Algorithm & 자료구조/자료구조

[알고리즘 JS] 퀵정렬 알고리즘 : Quick Sort Algorithm

퀵정렬 알고리즘이란? 하나의 기준점을 가지고 분할과 정복 방식으로 정렬하는 알고리즘이다. 최선의 경우 O(NlogN) 의 속도를 낼 수 있다. 아래 그림에서는 가장 오른쪽에 위치한 요소를 첫 번째 피봇 기준점으로 삼았지만, 전체 배열의 중간 요소를 초기 시작점으로 정하는 것이 일반적이다. 처음 정한 피봇을 기준으로 전체 배열 안에서 피봇의 위치를 확정할 수 있는데, 이 때 정렬은 피봇을 기준으로 좌측에 순서 상관 없이 피봇보다 작은 값, 우측으로 순서 상관 없이 피봇보다 큰 값이기 때문에 피봇에 대한 위치는 확정적이라고 할 수 있다. 한 번의 반복이 끝나면 피봇의 위치가 확정되고, 이 피봇의 위치를 기준으로 좌측, 우측이 분할되기 때문에 각 범위를 다시 재귀적으로 호출하여 최종적으로 정렬할 범위 안에 요..

[알고리즘 JS] 삽입 정렬 알고리즘 : Insertion Sort Algorithm

삽입 정렬 알고리즘이란? 요소가 들어있는 배열을 i 로 반복할 때, 현재 i 위치 좌측으로 이미 요소가 정렬된 상태이고, i 값과 좌측의 값들을 비교해 i의 적절한 위치를 찾아 삽입하는 정렬 알고리즘이다. 삽입 정렬 알고리즘 코드 적용 const nums = [11, 7, 5, 6, 10, 9]; function insertionSort(nums) { let N = nums.length; for (let i = 1; i < N; i++) { // i는 언제나 1번째부터 시작하고, temp 변수에 i의 현재 값을 보관한다. let temp = nums[i]; // j는 언제나 i - 1의 위치에서 시작한다. let j = i - 1; // 만약에 j 가 0 이상이고, i위치의 값보다 j위치의 값이 더 큰 ..

[알고리즘 JS] 버블 정렬 알고리즘 : Bubble Sort Algorithm

버블 정렬 알고리즘이란? 아래 그림의 주황색 부분 처럼, 인접한 두 개의 요소의 대소를 비교해 자리를 바꿔 정렬을 하는 알고리즘이다. 바깥쪽 반복과 안쪽 반복이 있을 때 바깥 반복을 배열의 길이만큼 반복하고, 안쪽 반복에서는 j로 0번째 인덱스부터 마지막요소를 제외한 범위만큼 반복하면서, 배열의 j번째 요소와 j + 1번째 요소의 대소를 비교한다. j + 1번째 요소와 비교되기 때문에 배열의 마지막 요소는 범위에 추가를 하지 않아도 저절로 반복이 된다. 위 그림처럼 정렬이 완료된 범위의 마지막 부분은 정렬 범위에서 제외시켜 주어도 되는데, 그렇게 하기 위해서 i 가 증가할 때마다 j의 범위에서 i만큼 감소시켜준다. 버블 정렬 알고리즘 코드 적용 const bubbleSort = function (arr)..

[알고리즘 JS] 이진 검색 알고리즘 : Binary Search Algorithm

유데미 쉽게 배우는 JavaScript 알고리즘 입문 강의의 내용을 정리한 글입니다. 검색 알고리즘이란? 검색 알고리즘이란 말 그대로 주어진 데이터 내에서 특정 데이터를 검색하여 찾아내는 알고리즘이다. 순차 검색 알고리즘, 이진 검색 알고리즘, 해쉬 탐색 알고리즘 등 종류가 많다. 검색 알고리즘이라고도 하고 탐색 알고리즘이라는 이름을 쓰기도 하는데, 강의에서 검색이라는 용어를 사용하셨기 때문에 나도 검색 알고리즘이라고 표기하겠다! 이진 검색 알고리즘이란? Divide and Conquer : "분할과 정복" 방식이라고 할 수 있는데, 정리하면 두 부분씩 쪼개어 범위를 좁혀가며 검색한다는 의미이다. 정렬되어 있는 데이터를 먼저 절반으로 나눈뒤, 절반에 위치한 데이터(mid 데이터)와 타겟 데이터를 비교한다..

[알고리즘 JS] 선택 정렬 알고리즘 : Selection Sort Algorithm

유데미 쉽게 배우는 JavaScript 알고리즘 입문 강의의 내용을 정리한 글입니다. 정렬 알고리즘이란? 일단 정렬 알고리즘이란, 말그대로 주어진 범위 내의 불규칙적으로 나열된 데이터들의 순서를 일정 기준으로 정렬해주는 알고리즘이다. 정렬 알고리즘에는 여러 종류가 있는데, 크게 선택 정렬, 버블 정렬, 퀵 정렬, 삽입 정렬, 병합 정렬 등이 있다. 그 중 가장 첫 번째로 다룰 선택 정렬 알고리즘은, 다른 정렬 알고리즘을 배우기 전에 간단하게 정렬 알고리즘을 경험해 볼 수 있는 알고리즘인 것 같다. (다른 정렬 알고리즘은 아직 몰라서...) 선택 정렬 알고리즘이란? 말 그대로 데이터 하나를 선택해서 해당 데이터를 기준으로 작거나(오름차순), 큰(내림차순) 데이터가 있는지 비교해 선택된 데이터와 계속해서 자..