강의: 구름에듀 "안경잡이개발자가 알려주는 실전 알고리즘 강좌"
링크: 안경잡이개발자가 알려주는 실전 알고리즘 강좌
(강의는 알고리즘 풀이를 C/C++ 언어로 진행합니다.)
내용 정리 출처
대체로 알고리즘을 공부할 때 가장 먼저 나오는 개념이 정렬 알고리즘인 이유는 효율성의 차이를 가장 극명하게 보여주기 때문
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법
특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누는 알고리즘
선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지기 때문에 데이터 개수가 많은 상황을 대비하여 일반적인 상황에서 사용하기 매우 어려운 알고리즘
- 피벗을 하나 선택한다.
- 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.
- 양 방향에서 찾은 두 원소를 교환한다.
- 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다.
- 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다. (Divide : 분할)
- 인접한 부분리스트끼리 합친다. (Conqure : 정복)
function swap (i, j, arr) {
const temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
/**
* 왼쪽 피벗 방식
* @param {Array<number>} arr 정렬할 배열
* @param {number} lo 현재 부분배열에서의 왼쪽
* @param {number} hi 현재 부분배열에서의 오른쪽
* @returns 정렬된 arr
*/
function quickSort (arr, left = 0, right = arr.length - 1) {
if (left >= right) {
return;
}
const mid = Math.floor((left + right) / 2);
const pivot = arr[mid];
const partition = divide(arr, left, right, pivot);
quickSort(arr, left, partition - 1);
quickSort(arr, partition, right);
function divide (arr, left, right, pivot) {
console.log(`arr: ${arr}, left: ${arr[left]}, pivot: ${pivot}, right: ${arr[right]}`)
while (left <= right) {
while (arr[left] < pivot) {
console.log("left", left);
left++;
}
while (arr[right] > pivot) {
console.log("right", right);
right--;
}
if (left <= right) {
console.log(left, right);
swap(left, right, arr);
left++;
right--;
}
}
return left;
}
return arr;
}
quickSort(arr1, 0, arr1.length - 1);
console.log(arr1);
참고) 코드가 간결하지만 메모리 공간의 낭비가 심한 in place 방식이 아닌 코드
function quickSort (array) {
if (array.length < 2) {
return array;
}
const pivot = [array[0]];
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] < pivot) {
left.push(array[i]);
} else if (array[i] > pivot) {
right.push(array[i]);
} else {
pivot.push(array[i]);
}
}
console.log(`left: ${left}, pivot: ${pivot}, right: ${right}`);
return quickSort(left).concat(pivot, quickSort(right));
}
const sorted = quickSort([5, 3, 7, 1, 9]);
console.log(sorted);
BigO
평균 O(nlog₂n)
- Worst Case: O(N^2)
- Best Case: O(log₂n)