🌱 Quick Sort ( 퀵 정렬 )
👉🏻 퀵 정렬(Quick-Sort) : 요소를 피벗(pivot)으로 선택하고 피벗을 정렬된 올바른 위치에 배치하여 선택한 피벗 주위에 주어진 배열을 분할하는 정렬 알고리즘 입니다. 다른 정렬보다 빠르게 정렬되어서 그대로 이름이 퀵 소트가 되었습니다.
- 피벗(pivot) : 피벗은 중심축 혹은 중심축을 중심으로 회전한다라는 의미를 가진 단어입니다. 퀵 정렬에서 피벗은 배열이나 리스트에서 정렬을 위해 선택하는 기준 요소로, 피벗을 기준으로 피벗보다 작은 값은 앞으로, 피벗보다 큰 값은 뒤로 보내어 리스트를 분할합니다. 즉, 리스트를 분할하는 기준값이 됩니다.
-
퀵 정렬은 다른 원소와의 비교만으로 정렬하는
비교 정렬 알고리즘입니다. -
배열이나 리스트 안에 같은 값이 있다면 퀵 정렬 후 순서가 달라질 수 있습니다. 따라서
불안정 정렬에 해당합니다. -
퀵 정렬은
분할 정복 알고리즘에 속합니다. 리스트를 쪼개어 정렬하는 알고리즘으로 대표적으로 퀵 정렬과 병합정렬이 이에 속합니다.- 병합정렬의 경우 리스트를 균등하게 반으로 나눕니다. 만약 배열의 길이가 10이라면 병합정렬은
5 : 5로 요소의 갯수가 균등하게 나눠집니다. - 퀵 정렬은 비균등하게 분할합니다. 같은 상황에서 퀵 정렬은 최악의 경우
1: 9에서부터 최선의 경우5 : 5까지 다양하게 나타날 수 있습니다.
- 병합정렬의 경우 리스트를 균등하게 반으로 나눕니다. 만약 배열의 길이가 10이라면 병합정렬은
☀️ Operations of Quick Sort ( 작동 )
Patitioning & Divide ( 분할 )
퀵 정렬은 주어진 리스트를 '파티셔닝'(partitioning) 으로 분할합니다.
정렬을 해야 할 리스트에서 임의의 수를 고릅니다. 이 수를 피벗(pivot) 이라 부르고, 나머지 수를 피벗과 비교하여 작은 숫자는 왼쪽으로 옮기고 큰 숫자는 오른쪽으로 옯깁니다.
🌿 피벗(Pivot)을 고르는 다양한 방법
최악의 상황(가장 큰 수나 가장 작은 수를 피벗으로 선택하는 상황)과 불균형 분할을 방지하기 위해 피벗 선택시 데이터가 균등하도록 다양한 방법을 제시합니다.
- 항상 첫번째 요소를 피벗으로 선택하는 방법
let pivot = arr[0];
- 항상 마지막 요소를 피벗으로 선택하는 방법
let pivot = arr[arr.length - 1];
- 가운데 요소를 피벗으로 선택하는 방법
let pivot = Math.floor((low + high) / 2);
- 임의의 요소를 피벗으로 선택하는 방법 👉🏻 후술
이 때 퀵 정렬은 먼거리의 데이터를 swap 할 수 있습니다. 이는 불필요한 데이터의 이동을 줄이며 퀵 정렬이 다른 정렬에 비해 빠른 이유가 됩니다.
이런 과정을 통해 피벗을 기준으로 왼쪽, 피벗, 오른쪽 으로 나뉘게 되는데, 이 후 피벗은 더이상 움직이지 않습니다. 즉, 파티셔닝의 결과로 피벗은 정렬된 위치에 존재하게 됩니다.
이러한 과정을 더 이상 나누는게 불가능할 때까지 반복합니다.
Conquer ( 정복 )
분할된 부분 리스트에 대해 재귀적으로 위의 과정을 반복합니다. 그러다가 분할한 리스트의 길이가 0이나 1이 되면, 더 이상 파티셔닝을 할 수 없습니다.
퀵 정렬을 한번 호출할 때마다, 최소 하나 이상의 숫자가 정렬됩니다. 즉, 피벗은 최종 위치에 도달하게 됩니다. 이는 퀵 정렬은 무한 루프에 빠질 일 없는 끝이 보장된 알고리즘임을 증명합니다. 호출할 때마다 리스트의 길이는 계속 줄어들고, 언젠가는 베이스 조건에 도달하게 됩니다.
길이가 0이나 1일 때는 이미 주어진 리스트가 정렬된 상태라고 할 수 있으므로, 이 때에는 그냥 주어진 리스트를 반환해주면 됩니다.
Combine ( 조합 )
분할한 부분 리스트에 계속해서 퀵 정렬을 실행하면 정렬된 배열이 나옵니다.
피벗의 왼쪽, 피벗, 오른쪽 리스트를 합쳐 나가면 정렬된 전체 리스트 결과로 만들어 집니다.
☀️ Implement of Quick Sort ( 구현 )
pivot으로 항상 첫번째 요소를 선택하는 경우를 기준으로 작성한 코드입니다.
👉🏻 Python으로 구현한 코드
# 항상 첫번째 요소를 pivot으로 선택하는 경우
def quickSort(arr):
# base case
if not arr: return [];
# partitioning & divide
left = [], right = [], pivot = arr[0];
for i in range(1, len(arr)):
if pivot > arr[i]: left.append(arr[i]);
else right.append(arr[i]);
# combine & recursive
return quickSort(left) + pivot + quickSort(right);👉🏻 JavaScript로 구현한 코드
// 항상 첫번째 요소를 pivot으로 선택하는 경우
const quickSort = (arr) => {
// base case
if(arr.length === 0) return [];
// partitioning & divide
const left = [], right = [], pivot = arr[0];
for(let i=1; i<arr.length; i++){
if(pivot > arr[i]) left.push(arr[i]);
else right.push(arr[i])
};
// combine & recursive
return quickSort(left).concat(pivot, quickSort(right));
}☀️ Time and Space Complexity Analysis ( 시·공간 복잡도 )
시간복잡도
최선 혹은 평균적으로는 O(n log n)만큼의 시간복잡도를 가집니다.
하지만 pivot으로 가장 작은 값이나 가장 큰 값을 선택하는 경우나, 이미 정렬이 되어있거나 거의 정렬이 된 리스트의 경우, 혹은 반대로 정렬된 리스트인 경우는 최악의 경우에 해당합니다. 이 때 퀵 정렬은 O(n^2)의 시간복잡도를 가지게 됩니다.
- 하지만 실질적으로 정렬할 때
O(n^2)만큼의 시간이 걸릴 확률이 거의 없도록 설계합니다.
🌿 최악의 시간복잡도를 방지하는 방법
- Randomization (배열의 랜덤화) : 배열의 랜덤한 두 개의 인덱스를 뒤바꿔주는 방식으로 정렬되어 있지 않도록 만듭니다.
- Random Pivot (랜덤 피벗 선택) : pivot을 선택할 때, 난수를 발생시켜 선택하는 방식입니다.
- Median Of Three Pivot : pivot의 후보로 3개의 요소를 뽑은 후에 그 중 중간값을 선택하는 방법입니다.
공간복잡도
평균적으로 O(log n)의 메모리를 필요로 합니다. 이는 재귀적인 호출로 생기는데, stack의 깊이가 요소 n개에 대해 O(log n)에 비례하여 상수가 되지 않습니다. 따라서 O(n)보다 적으므로 추가적인 메모리 공간을 필요로 하지 않아서 제자리 정렬이라고도 합니다. 최악의 경우에도 O(n)의 공간복잡도를 가집니다.
👀 Reference
