🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
정렬 - 퀵 정렬
📍 퀵 정렬(Quick Sort)
👉🏻 병합 정렬과 같이 분할 정복 알고리즘에 속함
👉🏻 즉, 재귀를 사용함
피벗
_
[5, 3, 7, 2, 6, 4, 9, 1, 8]
// 배열 중 하나를 피벗으로 설정
// 이해하기 쉽게 여기서는 제일 왼쪽 값을 피벗으로 설정
_ leftStartIndex _ rightStartIndex
[5, 3, 7, 2, 6, 4, 9, 1, 8]
_ _
left right
// leftStartIndex는 왼쪽에서 오른쪽으로 이동하다가 피벗보다 큰 수가 있으면 멈춤
// rightStartIndexs는 오른쪽에서 왼쪽으로 이동하는데 피벗보다 작은 수가 있으면 멈춤
// 둘 다 멈추면 값을 교환
피벗
_ _ _
[5, 3, 1, 2, 6, 4, 9, 7, 8]
_ _
[5, 3, 1, 9, 6, 4, 2, 7, 8]
_ _
[5, 3, 1, 2, 6, 4, 9, 7, 8]
[5, 3, 1, 2, 4, 6, 9, 7, 8] // leftStartIndex와 rightStartIndex가 만났음!
// 5와 비교해서 이동
[3, 1, 2, 4, 5, 6, 9, 7, 8]
__________ ___________
// 5를 기준으로 왼쪽은 더 작고, 오른쪽은 더 큼!
...
[1, 2, 3, 4, 5, 6, 7, 8, 9]
📍 퀵 정렬의 구현
[ quick_sort.mjs ]
function quickSort(arr, left, right) {
if(left <= right) {
let pivot = divide(arr, left, right); // 정렬된 피벗 위치(인덱스)를 리턴하는 함수 divide의 값을 저장
quickSort(arr, left, pivot - 1); // 왼쪽 영역 정렬
quickSort(arr, pivot + 1, right);
}
}
function divide(arr, left, right) {
let pivot = arr[left];
let leftStartIndex = left + 1;
let rightStartIndex = right;
while(leftStartIndex <= rightStartIndex) {
while(leftStartIndex <= right && pivot >= arr[leftStartIndex]) {
leftStartIndex++;
}
while(rightStartIndex >= (left + 1) && pivot <= arr[rightStartIndex]) {
rightStartIndex--;
}
if(leftStartIndex <= rightStartIndex) {
swap(arr, leftStartIndex, rightStartIndex);
}
}
swap(arr, left, rightStartIndex);
return rightStartIndex;
}
function swap(arr, index1, index2) {
let temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
let arr = [5, 3, 7, 2, 6, 4, 9, 1, 8];
console.log("===== 정렬 전 =====");
console.log(arr);
quickSort(arr, 0, arr.length - 1);
console.log("===== 정렬 후 =====");
console.log(arr);
👉🏻 퀵 정렬의 성능은 대부분 좋은 경우(Θ(nlogn))를 선택하고, 최악의 경우(O(n^2))가 발생할 확률이 낮음
👉🏻 즉, 퀵 정렬은 Θ(nlogn)의 성능을 가짐
📍 퀵 정렬의 장단점
👉🏻 장점: 정렬 알고리즘 중 가장 좋은 성능
👉🏻 단점: 이해와 구현이 어려움