[Algorithm] 퀵 정렬(Quick Sort)

1. 퀵 정렬(Quick Sort)이란?

• 찰스 엔터니 리처드 호어(C. A. R. Hoare)가 개발한 알고리즘으로, 일반적으로 폭넓게 사용되고 있는 빠른 정렬 알고리즘이다.
• 퀵 정렬은 대표적인 분할 정복을 사용한 알고리즘으로, 각 그룹에 대해 피벗(pivot) 설정과 그룹 나눔을 반복하여 정렬을 한다.
• 평균 시간 복잡도는 O(n log n)이다.
• 이미 정렬이 된 배열의 경우, 최악 시간 복잡도는 O(n ^2)이다. (이 경우 삽입 정렬 사용)

이미지 출처: https://miro.medium.com/max/610/1*c8FT6a4d8bdZMxqYOxPL9A.png

2. 동작 방식

퀵 정렬을 사용하여 배열을 정렬한다면 아래와 같이 동작한다. 배열은 { 5, 7, 1, 4, 6, 2, 3, 9, 8 }이다.

1. 배열의 첫번째 원소를 피벗(pivot)으로 선택하여 배열을 나눈다.
2. 왼쪽에서 오른쪽으로 스캔하며 피벗보다 큰 값을 선택한다. (arr[start] >= pivot)
3. 오른쪽에서 왼쪽으로 스캔하며 피벗보다 작은 값을 선택한다. (arr[end] <= pivot)
4. 피벗보다 큰 값과 피벗보다 작은 값을 교환한다. 
5. 작은 값의 인덱스가 큰 값의 인덱스보다 작은 경우(엇갈린 경우), 피벗보다 작은 값과 피벗을 교환한다. 
6. 위 과정을 재귀적으로 호출한다. (피벗 이하의 값은 왼쪽으로 이동하고 피벗 이상의 값은 오른쪽으로 이동)

2.1 동작 예시

3 7 8 1 5 9 6 10 2 4 --> 7,2 교환

3 2 8 1 5 9 6 10 7 4 --> 8,1 교환

3 2 1 8 5 9 6 10 7 4 --> 엇갈린 경우: 작은 값과 피벗을 교환

1 2 3 8 5 9 6 10 7 4 --> 피벗을 기준으로 분할 정복

1 2 3 8 5 9 6 10 7 4

1 2 3 8 5 9 6 10 7 4

1 2 3 8 5 4 6 10 7 9

1 2 3 8 5 4 6 7 10 9 --> 엇갈린 경우: 작은 값과 피벗을 교환

1 2 3 7 5 4 6 8 10 9

...

3. 구현하기

public void quickSort(int[] arr,int start, int end) {
  int group = partition(arr, start, end); // pivot
  if(start < group-1) quickSort(arr, start, group - 1);
  if(end > group) quickSort(arr, group, end);
}

public int partition(int[] arr,int start,int end) {
  // 그룹을 나누는 동작을 수행
  int pivot = arr[(start + end) / 2];
  while(start <= end) {
    while(arr[start] < pivot) start++;
    while(arr[end] > pivot) end--;
    if(start <= end) {
      swap(arr, start, end);
      start++;
      end--;
    }
  }
  return start;
}

public void swap(int[] arr,int start,int end) {
  int tmp = arr[start];
  arr[start]=arr[end];
  arr[end]=tmp;
  return;
}


// 호출 
int[] arr= {7,4,2,8,3,5,1,6,10,9};
quickSort(arr, 0, arr.length - 1);

4. 피벗 선택하기

아래와 같이 피벗을 설정할 경우, 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 때 스캔하는 요소를 줄일 수 있다. 따라서 더 빠른 속도로 정렬할 수 있다.

4.1 피벗 선택하는 방법

1. 나눌 배열의 처음(start), 가운데(middle), 끝(end) 요소를 정렬한다.
2. 가운데 요소와 끝에서 두번째 요소를 교환한다.
3. 피벗으로 끝에서 두번째 요소를 선택하고 나눌 대상의 범위를 arr[left + 1] ~ arr[right - 2]로 좁힌다.

4.1 피벗 선택 예시

배열이 { 8, 7, 6, 5, 4, 3, 2, 1, 0 }인 경우, 처음 요소는 8, 중간 요소는 4, 끝 요소는 0이다.

가운데 요소(4)와 끝에서 두번째 요소(1)을 교환한다. --> { 8, 7, 6, 5, 1, 3, 2, 4, 0 }

끝에서 두번째 요소(4)를 피벗으로 한다.