코딩 테스트 공부 - 퀵 정렬(백준 11004번)

시간 복잡도 - $ O(n\log(n)) $

 

퀵 정렬

기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘.

기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미칠 수 있음.(최악의 경우 $ O(n^{2}) $)

피벗(pivot)을 설정해 부분 배열로 나누고 재귀적으로 정렬해가는 과정

#include <vector>
using namespace std;

void quick_sort(vector<int> &A, int S, int E, int K);
int partition(vector<int> &A, int S, int E);
void swap(vector<int> &A, int S, int E);

void quick_sort(vector<int> &A, int start, int end, int K) {
  int pivot = partition(A, start, end);
  if (pivot == K)
    return;
  else if (K < pivot) {
    quick_sort(A, start, pivot - 1, K);
  } else {
    quick_sort(A, pivot + 1, end, K);
  }
}

int partition(vector<int> &A, int start, int end) {
  if (start + 1 == end) {
    if (A.at(start) > A.at(end))
      swap(A, start, end);
    return end;
  }

  int M = (start + end) / 2;
  swap(A, start, M);
  int pivot = A.at(start);
  int i = start + 1;
  int j = end;
  while (i <= j) {
    while (j > 0 && A.at(j) > pivot)
      j--;
    while (i < A.size() - 1 && A.at(i) < pivot)
      i++;
    if (i <= j)
      swap(A, i++, j--);
  }
  A.at(start) = A.at(j);
  A.at(j) = pivot;
  return j;
}

void swap(vector<int> &A, int S, int E) {
  int temp = A.at(S);
  A.at(S) = A.at(E);
  A.at(E) = temp;
}

 

퀵 정렬은 중복된 키 값이 존재하는 경우 순서대로 바뀌지 않을 수 있기 때문에 stable 하지는 않다.

 

첫 째, 피벗의 값을 잘 선정하는 것이 빠른 속도에 도움이 된다.

둘 째, 부분 배열로 나눈 후 재귀적으로 호출해 정렬해나가는 과정이다.

셋 째, 중복된 키 값이 존재하는 경우 start와 end  비교 시 $ <= $ 연산을 사용하는 것이 좋다.