퀵 정렬
- 정렬 알고리즘 중 가장 많이 사용되는 알고리즘.
- 퀵 정렬만큼 빠른 알고리즘에는 "병합 정렬" 알고리즘이 있으며 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.
- pivot(기준 데이터)를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿔 정렬한다.(큰 데이터가 없을 수도 있고 작은 데이터가 자신과 같은 값일 수도 있다. 케이스들을 아래에서 자세히 다뤄보자.)
- 퀵 정렬을 수행하기 전에 피벗을 어떻게 설정할 것인지 미리 명시해야 한다.
- 피벗을 설정하고 리스트를 분할하는 방법에 따라 여러 방식으로 나뉘는데, 대표적으로 호어 분할(Hoare Partition)방식이 있다.
호어 분할(Hoare Partition)은 리스트에서 첫 번째 데이터를 pivot으로 정한다.
퀵 정렬 수행과정
- 피벗을 설정한다.
- 왼쪽에서 부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
피벗보다 큰 데이터를 발견하지 못하는 경우, 피벗과 작은 데이터의 위치를 변경한다.
피벗보다 작은 데이터를 찾을 때는, 피벗보다 작거나 같은 경우라고 생각해야 한다.
(= 작은 데이터가 없을 때는 자신이 작은 데이터가 된다) - 큰 데이터와 작은 데이터를 찾았다면 서로의 위치를 교환한다.
만약 큰 데이터와 작은 데이터의 위치가 엇갈리면, 작은 데이터(작거나 같은 데이터)와 피벗의 위치를 변경한다. - 위 과정을 반복하면 피벗에 대한 정렬이 수행된다.
다음 예를 통해 살펴보자. 출처: 네이버 지식백과
① 맨 앞의 20을 기준키로 하고, 기준키 다음부터 기준키보다 큰 데이터를 찾아 50을 선택하고, 마지막 데이터부터 기준키보다 작은 데이터를 찾아 5를 선택한다. 그리고 선택된 50과 5를 교환한다.
② 계속해서 진행하여 기준키보다 큰 데이터인 40을 선택하고, 기준키보다 작은 데이터인 19를 선택한다. 그리고 두 수를 교환한다.
③ 마찬가지로 진행하여 기준키보다 큰 데이터인 40과 기준키보다 작은 데이터인 9를 선택한다. 그런데 발견된 위치가 서로 교차하는데, 이런 경우에는 두 값을 교환하지 않고 기준키 20과 작은 데이터인 9를 교환한다. 또한 기준키보다 큰 데이터를 발견하지 못하는 경우에도 기준키와 작은 데이터를 교환한다.
④ 데이터들을 보면 기준키 20을 기준으로 왼쪽에는 기준키보다 작은 데이터들이, 오른쪽에는 큰 데이터들이 있음을 알 수 있다. 이때 기준키를 중심으로 양분한다.
이제부터는 기준키를 중심으로 왼쪽 데이터들에 대해 그리고 오른쪽 데이터들에 대해 같은 방법으로 동작한다. 먼저 왼쪽 데이터들에 대해 동작하는 과정을 살펴보자.
⑤ 기준키 9보다 큰 데이터인 18과 작은 데이터인 5를 선택하고 교환한다.
⑥ 마찬가지로 진행하여 큰 데이터인 18과 작은 데이터인 5를 선택하는데, 발견된 위치가 교차되므로 기준키 9와 작은 데이터인 5를 교환한다.
⑦ 그리고 기준키 9를 중심으로 양분한다.
⑧ {18, 19}에 대해 기준키 18보다 큰 데이터인 19와 기준키와 작거나 같은(같은 것도 포함됨) 데이터인 18을 선택하는데, 발견된 위치가 교차되므로 기준키 18과 기준키보다 작거나 같은 18을 교환한다.
⑨ 그리고 양분한다.
⑩ 이제 {40, 50, 25}에 대해 동작하게 되어 기준키 40보다 큰 50과 작은 25를 선택한다. 그리고 이 두 수를 교환한다.
⑪ 다음으로 큰 데이터인 50과 작은 데이터인 25를 선택하는데, 교차하므로 기준키 40과 작은 데이터인 25를 교환한다.
⑫ 그리고 기준키 40을 기준으로 양분한다. 모든 동작이 완료된다.
자바스크립트 예시
let array=[1,5,7,2,3,6,8,0,9,4]
const quickSort = function(array, start, end){
if(start >= end){return;}
let pivot = start;//pivot
let left = start + 1;//큰 수
let right = end;//작은 수
while(left <= right){//엇갈릴때까지 계속
while(left <= end && array[left] <= array[pivot]){
left++;//큰 수를 찾을 때까지 반복, 큰 수가 없다면 인덱스는 end+1이다.
}
while(right > start && array[right] >= array[pivot]){
//보다 왼쪽에 작은 수가 있을 수도 있기 때문에
//"array[right] = array[pivot]"일때도 pass한다.
//차피 작은 수가 없다면 right는 start(pivot)이다
right--;//작은 수를 찾을때까지 반복, 작은 수가 없다면 인덱스는 start이다.
}
if(left > right){
//엇갈릴때(큰 수가 없는 경우, 작은 수가 없는경우(= 작은 수가 피벗)도 포함)
let temp = array[right];
array[right] = array[pivot];
array[pivot] = temp;
}else{
//엇갈리지 않으면 큰 수와 작은 수를 교환
let temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
quickSort(array, start, right-1);
quickSort(array, right+1, end);
}
quickSort(array,0,array.length-1);
console.log(array);
//출력: [0,1,2,3,4,5,6,7,8,9]