2021/05(15)
-
[알고리즘] 정렬 - 빠른 정렬(퀵정렬, Quick Sort) (자바스크립트/javascript/node.js)
빠른 정렬(퀵 정렬, Quick Sort) 빠른 정렬(퀵 정렬)은 기준점을 획득한 다음 해당 기준점을 기준으로 배열은 나눈다. (한 쪽에는 기준점보다 작은 항목들이 위치하고 다른 쪽에는 기준점보다 큰 항목들이 위치한다.) 이런 식으로 모든 항목이 정렬될 때까지 이 과정을 반복한다. 우선 기준점을 나타내는 변수를 pivot이라고 지정하고, 기준점을 기준으로 왼쪽에는 기준점보다 작은 항목들이 위치하도록 하고 오른쪽에는 기준점보다 큰 항목들이 위치하도록 한다. 나뉘어진 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하여, 모든 배열이 기본 배열(요소가 하나뿐인 배열)이 될 때까지 반복하면 된다. 이 때 기준점을 정하는 기준은 없으며 보통의 경우에는 배열의 첫번째 원소 / 배열의 마지막 원소 / 물리적으로 중앙에 ..
2021.05.04 -
[알고리즘] 정렬 - 버블 정렬(거품 정렬, Bubble Sort) (자바스크립트/javascript/node.js/알고리즘)
버블 정렬(거품 정렬, Bubble Sort) 버블 정렬이란? 버블 정렬은 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 시간 복잡도 O(n^2) 공간 복잡도 O(1) 장점 in-place 알고리즘이기 때문에 메모리가 절약된다. 구현하기가 쉽다. 단점 다른 정렬 알고리즘은 배열의 이미 정렬된 부분을 활용하는데 비해 거품 정렬은 모든 가능한 짝을 비교하기 때문에 성능이 안좋은 정렬 중에서도 가장 안좋은 편에 속한다. function bubbleSort(array) { let temp; for (let i = 0; i < array.length - 1; i++) { for (let j = 0; j..
2021.05.03 -
[알고리즘] 정렬 - 삽입 정렬(Insertion Sort) (자바스크립트/node.js/javascript/알고리즘)
삽입 정렬 삽입 정렬이란? 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다. 동작 과정 예를 들어 [3, 7, 2, 5, 1, 4]의 배열을 오름차순으로 정리한다고 하면 첫번째 숫자는 놔두고 두번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣는다. 세번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣는다. 이렇게 끝까지 계속 한다. 시간 복잡도 Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우 Best Case: O(n): 이미 정렬이 되어있는 경우 공간 복잡도 O(1) 장점 메모리가 절약된다. (배열을 새로 만들 필요 없이 주어진 배열 안에서 정렬시키면 되기 때문, in pla..
2021.05.03