퀵 정렬 알고리즘을 이용해 오름차순으로 정렬하는 함수

퀵 정렬

퀵 정렬(quick sort)은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 합병 정렬과 같이 분할-정복법(divide and conquer)을 사용한다. 그러나 합병 정렬과는 달리 리스트를 균등하지 않게 분할한다.

먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피벗으로 하자. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고, 오른쪽은 피벅보다 큰 요소들로 구성된다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

퀵 정렬의 평균적인 경우의 시간 복잡도가 으로 나타난다. 특히 다른 의 정렬 알고리즘과 비교하였을 때도 가장 빠른 것으로 나타났다. 이는 퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성 등에서 기인한다고 보인다.

퀵 정렬은 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는 등의 장점이 있는 반면에 정렬된 리스트에 대해서는 오히려 수행 시간이 더 많이 걸리는 등의 단점도 가진다. 이러한 불균형 분할을 방지하기 위하여 피벗을 선택할 때 단순히 리스트의 왼쪽 데이터를 사용하는 대신에 보다 리스트의 중앙 부분을 분할할 수 있는 데이터를 선택한다. 많이 사용되는 방법은 리스트 내의 몇 개의 데이터 중에서 중간값(median)을 피벗으로 선택하는 것이다.

일반적으로 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 중간값을 선택하는 방법(median of three)이 많이 사용된다. 

---

// 배열의 세 값중 중간값의 인덱스를 반환하는 함수

static int medianIndex(int A[],int left, int mid, int right) {

if (A[left] > A[mid]) {

if (A[mid] > A[right]) return mid;

else if (A[left] > A[right]) return right;

else return left;

}

else {

if (A[left] > A[right]) return left;

else if (A[mid] > A[right]) return right;

else return mid;

}

}

// 퀵 정렬에서 partition() 함수

static int partition(int A[], int left, int right) {

int low = left;

int high = right + 1;

int min = medianIndex(A, left, (left + right) / 2, right); //중간값의 인덱스 선택

swap(A[left], A[min]); // 중간값의 인덱스를 왼쪽 데이터와 교환

int pivot = A[left]; // 피벗 설정

do {

do { // 왼쪽 리스트에서 피벗보다 클 레코드 선택

low++;

} while (low <= right && A[low] < pivot);

do {

high--; // 오른쪽 리스트에서 피벗보다 큰 레코드 선택

} while (high >= left && A[high] > pivot);

if (low < high) // 선택된 두 레코드 교환

swap(A[low], A[high]);

} while (low < high); // 인덱스 low, right 가 엇갈리지 않는 한 반복

swap(A[left], A[high]); // 인덱스 high 가 가리키는 레코드와 피벗 교환

return high;

}

// 퀵 정렬 알고리즘을 이용해 배열의 left ~ right 항목들을 오름차순으로 정렬하는 함수

void quickSort(int A[], int left, int right) {

if (left < right) { // 정렬 범위가 2개 이상인 경우

int  pivot = partition(A, left, right); // 좌우로 분할

quickSort(A, left, pivot - 1); // 왼쪽 부분리스트를 퀵 정렬

quickSort(A, pivot + 1, right); // 오른쪽 부분리스트를 퀵 정렬

}

}