퀵 정렬 (Quick Sort) 알고리즘

 

 

 

 

분할 정복에 기반한 알고리즘.
리스트에서 피봇을 고른 뒤, 피봇을 기준으로 왼쪽에는 피봇보다 작은 수,

오른쪽에는 피봇보다 큰 수들을 모은 뒤, 비균등하게 리스트를 나눠가며 정렬한다.
리스트를 모두 쪼갰을 때 모두 정렬이 되어 있다.
따라서 마지막에는 정렬된 것을 합치기만 하면 된다.

리스트의 첫째 원소를 피봇으로 삼고, 나머지 리스트에서 왼쪽에서 시작하는 인덱스 low와 오른쪽에서 시작하는 인덱스가 high가 있다.
low는 피봇보다 값이 크거나 같은 원소를 만날 때까지 계속 오른쪽으로 이동한다. 즉, low보다 작은 인덱스의 원소들은 모두 값이 low가 가리키는 원소보다 작다.
high는 피봇보다 값이 작거나 같은 원소를 만날 때까지 계속 왼쪽으로 이동한다. 즉, high보다 큰 인덱스의 원소들은 모두 값이 high가 가리키는 원소보다 크다.
그러고 나서 low와 high가 서로 지나치지 않았다면
low는 피봇보다 값이 크거나 같은 원소를 가리키고 있고,
high는 피봇보다 값이 작거나 같은 원소를 가리키고 있다.
두 인덱스가 가리키는 원소를 서로 스왑한다.
두 인덱스의 대소 관계가 깨질 때까지 이 과정을 반복한다.
그러고 난 후에 high가 가리키는 원소와 피봇을 서로 스왑한다.
이렇게 되면 피봇을 기준으로 왼쪽에는 피봇보다 작은 원소들이, 오른쪽에는 피봇보다 큰 원소들이 자리하게 된다.
이 상태로 왼쪽 리스트와 오른쪽 리스트 각각에 대해 위의 과정을 재귀 호출한다.

수도코드
quick_sort(int a[], int left, int right){
  if(left == right) return;
  // 리스트를 비균등 분할
  int pivot = a[left];
  int low = left, high = right + 1;
  do{
    do{ low++; } while(low <= right && a[low] < pivot);
    do{ high--; } while(left <= high && a[high] > pivot);
    if(low < high) swap(a[low], a[high]);
  } while(low < high);
  swap(a[left], a[high]);
  // 두 리스트 각각에 대해 재귀 호출
  quick_sort(a, left, high - 1);
  quick_sort(a, high + 1, right);
}

시간 복잡도 : 분할 단계가 log n 개이고, 각 단계마다 비교 횟수가 n개이므로 시간 복잡도는 O(n log n)이다.
다만, 리스트가 극도로 불균형하게 나뉘는 경우(특히, 이미 정렬된 리스트에 퀵 정렬을 실행할 경우)
분할 단계가 n개가 되어버려서 최악의 경우로 시간 복잡도가 O(n^2)이 된다.