🗸 퀵 정렬이란 ?
퀵 정렬(Quick Sort)은 병합 정렬과 마찬가지로 분할 정복 (Divide and Conquer) 방식을 이용한 정렬 알고리즘이다.
간단히, 기준점 Pivot 을 정하고 배열의 한 쪽으로는 Pivot 보다 작은 값을, 다른 쪽으로는 Pivot 보다 큰 값을 정렬해 나가는 방식이다.
🗸 시간복잡도
- 평균 :
- 최악 :
시간복잡도 을 가지는 말 그대로 빠른 정렬 알고리즘이다.
🗸 단점
퀵 정렬은 Pivot 값을 임의로 선택하게 되는데 그 과정에서 만약 그 배열의 최대값이나 최소값을 선택하게 될 경우 분할이 효율적으로 이루어지지 않게 되어 최악의 경우 의 시간 복잡도를 가질수 있다. 또한 동일한 정렬 기준을 가지는 값에 대해서 처음 위치를 보장하지 않는다. (불안정 정렬, Unstable)
단점을 개선하기 위한 최적화 방법이 몇가지 있지만, 대표적으로 Pivot 값을 선택하는 방법을 한쪽으로 치우치지 않게 선택하는 방법으로 분할이 효율적으로 이루어지지 않는 문제에 대해서는 개선을 할 수 있다.
🗸 예시
Pivot값을 선택하는 방법은 여러가지가 있지만 이 예시에서는 배열의 가운데 값을Pivot으로 정한다.
규칙은 다음과 같다.
- 배열의 왼쪽 끝에서
Pivot보다 큰 값을 찾을 때 까지 한 칸씩 오른쪽 이동한다.- 배열의 오른쪽 끝에서
Pivot보다 작은 값을 찾을 때 까지 한 칸씩 왼쪽으로 이동한다.
왼쪽
8이Pivot인4보다 크므로, 바로STOP.
오른쪽
- 한 칸 이동한 후
0이Pivot보다 작으므로STOP.
STOP하였을때 아직i와j가 교차하지 않았으므로8과0을 스왑한다.- 같은 방법으로 한 칸씩 이동하며 다시
Pivot왼쪽에서는Pivot보다 큰 값, 오른 쪽에서는Pivot보다 작은 값을 찾았을때 , 아직 교차하지 않았으므로 두 값을 스왑한다.
위 방법으로 진행하다가,
i와j가 교차(i < j)하면 루프를 종료한다.
루프 종료 후, 배열의
LEFT~j,i~RIGHT로 배열을 분할한다.
이때, 만일Pivot기준 왼쪽 배열이 정렬이 잘 되어있어j가LEFT와 만난다면 왼쪽 배열은 더 이상 정렬하지 않는다.
마찬가지고 만일Pivot기준 오른쪽 배열이 정렬이 잘 되어있어i가RIGHT를 만난다면 오른쪽 배열은 더이상 정렬하지 않는다.
분할된 두 배열에서 다시
Pivot값을 정하고 왼쪽에서Pivot큰 값, 오른쪽에서Pivot보다 작은 값을 찾아 스왑하는 과정을 반복한다.
더 이상 분할 정복이 가능하지 않으면 배열을 반환한다.
🗸 자바스크립트로 구현
이러한 퀵 정렬을 자바스크립트로 구현하면 다음과 같다.
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[Math.floor(arr.length / 2)];
const left = arr.filter((item) => item < pivot);
const right = arr.filter((item) => item > pivot);
return [...quickSort(left), pivot, ...quickSort(right)];
}
function quickSort(arr, left = 0, right = arr.length - 1) {
if (arr.length <= 1) {
return arr;
}
const pivotIndex = Math.floor((left + right) / 2);
const pivot = arr[pivotIndex];
let i = left;
let j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (pivot < arr[j]) {
j--;
}
if (i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
}
if (left < j) {
quickSort(arr, left, j);
}
if (i < right) {
quickSort(arr, i, right);
}
return arr;
}
const arr = [8, 20, -2, 4, -6, 0, 5];
const sorted_arr = quickSort(arr);
console.log(sorted_arr) // [-6, -2, 0, 4, 5, 8, 20]
🗸 느낀점
눈으로만 볼떈 병합 정렬과 마찬가지로 재귀함수를 통해 배열을 분할하고 정렬한 후 합쳐나가는 과정이 머릿속으로 쉽게 이해가 가지 않았다. 직접 그림을 그려보고 한칸 한칸 이동시켜가며 처음부터 끝까지 정렬하는 과정을 진행시켜보니, 스왑과정과 루프의 i++, j--의 의미, 분할하는 과정 , 왜 퀵 정렬의 최적화 방법 중 하나가 Pivot 값을 랜덤하게 뽑는것인지 등이 이해가 되었다.
