💡 자바스크립트 언어로 자료구조 & 알고리즘에 대해 배운 내용을 기록합니다
📖 Intro
이전에 알아보았던 bubble, insertion, selection 정렬은 전반적으로 O(n^2) 의 시간복잡도를 가지므로, 배열의 길이가 커졌을때 상당히 비효율적인 알고리즘이 됩니다.
이러한 시간복잡도를 O(n logn)으로 개선할 수 있는 정렬 알고리즘들이 있습니다. 대표적인 것들이 Merge, Quick, Radix Sort인데요, 이 알고리즘들은 보다 더 효율적이지만, 그만큼 구현하기에 더 복잡하다는 점이 있습니다.
이번 포스트에서는 퀵 정렬 (Quick Sort)의 작동 방식을 알아보면서 자바스크립트 코드로 구현해보겠습니다.
📖 퀵 정렬 (Quick Sort)
- 병합 정렬처럼, 길이가 0이나 1인 배열은 항상 정렬되어 있는 상태라는 점을 활용합니다
- 하나의 요소를 Pivot 으로 선택해서, 정렬되 배열에서 pivot이 몇번째 인덱스에 위치해야 하는지 찾아가는 방식으로 작동합니다!
- 한번 Pivot이 적절한 위치에 배치되면, Pivot 양쪽에 모든요소들에 Quick sort를 적용합니다
Pivot Function
- Quick sort를 구현하려면, 먼저 Pivot 양쪽에 있는 배열에서 요소를 정렬하는 기능을 구현하는 것이 유용합니다.
- 배열이 주어지면, 이 함수는 하나의 요소를 Pivot으로 지정해야 합니다
- 다음 모든 요소들을 재배치해서, Pivot 보다 작은 요소들은 왼쪽에, Pivot보다 큰 요소들은 오른쪽에 배치합니다
- 이 때 양 쪽에 배치된 요소들의 순서는 그대로 갑니다
- 이 함수는 새 배열을 만들지 않아야 합니다.
Pivot Picking
- 퀵 정렬의 런타임은 피벗을 선택하는 방법에 따라 달라집니다
- 정렬하려는 데이터 셋의 대략적인 중간 값을 Pivot으로 선택하는 것이 이상적입니다.
- 우선 단순하게 하기 위해 항상 피벗을 첫 번째 요소로 선택하겠습니다.
Quicksort Pseudocode
- 인자 세 개를 받습니다 : 배열, 시작 인덱스(default 0), 종료 인덱스(default 배열길이-1)
- 시작 인덱스를 Pivot으로 설정합니다
- 현재 Pivot 인덱스를 변수에 저장합니다 ( Pivot이 종료되어야 할 위치를 찾아갑니다 )
- 배열의 시작부터 종료지점까지 반복합니다
- Pivot이 현재 값보다 더 크다면, pivot 인덱스를 증가시키고, 현재 요소와 pivot 인덱스의 요소의 위치를 바꿔줍니다
- 시작 요소와 Pivot 인덱스의 요소 위치를 바꿔줍니다
- pivot 인덱스를 리턴합니다
function pivot (arr, start = 0, end = arr.length - 1, i++) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]);
}
// 일단 피벗이 항상 첫번째 요소라고 가정합니다
let pivot = arr[start];
let swapIdx = start;
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIdx++;
swap(arr, swapIdx, i);
}
}
// start와 swapIdx의 위치를 바꿔줍니다
swap(arr, start, swapIdx);
return swapIdx;
}
// [3,1,6,8,2,4]
// -> return 2 --> [2,1,3,8,6,4]quicksort pseudocode
- 주어진 array에 위에서 구현한 pivot함수를 실행합니다
- 함수가 업데이트된 pivot 인덱스를 리턴하면, 해당 인덱스의 왼쪽 부분과 오른쪽부분에 재귀적으로 pivot 함수를 호출한다
- left, right의 요소가 2개 미만일때 함수의 호출이 멈춘다
function quickSort(arr, left = 0, right = arr.length-1) {
if (left < right) {
let pivotIndex = pivot(arr, left, right)
//left
quickSort(arr, left, pivotIndex-1);
//right
quickSort(arr, pivotIndex+1, right);
return arr;
}
}📖 시간복잡도
📖 Reference
Visualgo
Sorting Algorithm Animations
Udemy - Javascript Algorithms and Data Structures Masterclass
Frontend Developer