[알고리즘] 퀵 정렬(Quick Sort)

---

퀵 정렬 기본

• 합병 정렬(Merge Sort) 와 유사하게 분할 정복(Divide & Conquer) 방식 사용
• 기준(피벗)을 설정한 후 큰 수와 작은 수를 교환한 후 배열을 반으로 나누는 방식으로 동작
• 속도가 매우 빠르며, 추가적인 메모리 공간을 필요로 하지 않음
• 불균형 분할이 많아질 경우 속도가 느려질 수 있음(최악의 경우)
  • 이를 방지하기 위해 세 값의 중위법을 사용하여 피벗을 선택하는 경우가 많음

---

정렬 과정

1. 주어진 배열에서 피벗(pivot) 을 선정
2. 피벗을 기준으로 작은 값들이 모인 배열과 큰 값들이 모인 배열로 배열을 2등분
3. 해당 피벗을 기준으로 배열을 나누고 나면 피벗은 고정됨(재귀 호출 시 마다 피벗의 위치가 매번 고정되므로 이 알고리즘이 반드시 끝나는 것을 보장함)
4. 분할된 두 배열에서 1~3의 과정을 반복함

과정 예시

3 7 6 5 1 4 2 : 초기배열

pivot = 3

3 7 6 5 1 4 2 : low = 1, high = 6, swap!

3 2 6 5 1 4 7 : low = 2, high, = 5

3 2 6 5 1 4 7 : low = 2, high = 4, swap!

3 2 1 5 6 4 7 : low = 3, high = 3

3 2 1 5 6 4 7 : low = 3, high = 2 (서로 지나침) => high 와 pivot swap!

1 2 3 5 6 4 7

pivot = 1

...

pivot = 5

...

---

시간 복잡도

• 평균의 경우 : $O(Nlog_2N)$
• 최악의 경우 : $O(N^2)$

---

구현

정복(Conquer)

부분 배열을 정렬함
부분 배열의 크기가 충분히 작지 않으면, 재귀 호출을 이용하여 다시 분할 정복 방법을 적용

void quickSort(int[] arr, int start, int end) {
  if (start < end) { // 배열의 크기가 충분히 작아 질 때 까지 나눔
    int p = partition(arr, start, end); // 파티션을 적용 했을 때 피봇의 인덱스를 구함

    quickSort(arr, start, p - 1); // 처음 부터 피봇 전,
    quickSort(arr, p + 1, end); // 피봇 후 부터 마지막 까지 다시 퀵소트를 함
  }
}

분할(Divide)

입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할함
피벗을 중심으로 왼쪽은 피벗보다 작은 요소, 오른쪽은 피벗보다 큰 요소

int partition(int[] arr, int start, int end) {
  int low = start + 1; // pivot을 맨 왼쪽 값으로 할것이기 때문에 그 다음 값부터 확인
  int high = end;
  int pivot = arr[start]; // 가장 왼쪽 값을 pivot으로 설정

  while (low <= high) { // 양쪽에서 탐색하면서 둘이 겹쳐져 지나칠때 까지 한다.
    while (low <= end && arr[low] < pivot) { // 앞에서 부터 비교중 pivot 보다 크면 stop
      low++;
    }
    while (high >= start && arr[high] > pivot) { // 뒤에서 부터 비교중 pivot 보다 작으면 stop
      high--;
    }
    if (low < high) { // low , high 가 겹쳐져 지나친게 아니면 둘을 바꿔줌
      swap(arr, low, high);
    }
  }
  swap(arr, start, high); // 마지막으로 pivot과 high index의 값을 바꾸면 high index 가 pivot의 index가 됨
  return high; // pivot 위치 반환
}

void swap(int[] arr, int i, int j) {
  int temp = arr[j];
  arr[j] = arr[i];
  arr[i] = temp;
}

---