Quicksort
퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
Algorithm
퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.
- 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
내부 분할 알고리즘
Pascal과 C와 같은 명령형 언어에서는 대부분 이와 같은 내부 분할을 이용해 구현한다.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int len;
// Sorting in non decreasing order
void printArray(int arr[])
{
for (int i = 0; i < len; i++)
printf("%d ",arr[i]);
printf("]\n");
}
void swap(int arr[], int k, int small)
{
int temp;
temp = arr[k];
arr[k] = arr[small];
arr[small] = temp;
}
int partition(int arr[],int i,int j)
{
int pivot = arr[j];
int small = i-1;
for(int k = i;k<j;k++) {
if(arr[k] <= pivot) {
small++;
swap(arr,k,small);
}
}
swap(arr,j,small+1);
printf("Pivot = %d \n[",arr[small+1]);;
printArray(arr);
return small+1;
}
void quickSort(int arr[],int i,int j)
{
if(i < j) {
int pos = partition(arr,i,j);
quickSort(arr,i,pos-1);
quickSort(arr,pos+1,j);
}
}
int main()
{
int arr[] = {9,4,8,3,1,2,5};
len=sizeof(arr)/sizeof(int);
printf("Initial Array [");
printArray(arr);
quickSort(arr,0,len-1);
return 0;
}
Simple example
Quicksort_partition_-_example.png 아래는 Wikipedia 에서 구현된 버전이다.
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}