퀵 정렬

퀵 정렬이란?

퀵 정렬은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘입니다.

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬합니다. 리스트 안에서 하나의 원소를 피벗(pivot)으로 선택합니다. 그리고 피벗보다 작은 원소는 모두 피벗의 왼쪽으로, 그리고 큰 원소는 모두 피벗의 오른쪽으로 옮깁니다. 이제 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬합니다. 이 과정을 분할이 더 이상 이루어지지 않을 때까지 반복합니다.

분할 정복 방법: 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 (대게 순환 호출 이용)

동작 과정

1. 리스트 안에서 하나의 원소를 피벗(pivot)으로 선택합니다.
2. 피벗을 기준으로 왼쪽에는 피벗보다 작은 원소, 오른쪽에는 피벗보다 큰 원소들이 오도록 피벗을 이용하여 리스트를 둘로 분할합니다.
3. 분할된 두 리스트에 대해 각각 위의 과정을 재귀적으로 반복합니다.
4. 분할이 더 이상 이루어지지 않으면 정렬이 완료됩니다.

특징

1. 불안정 정렬 + 비교 정렬

2. 매우 빠른 속도로 수행

3. 병합 정렬과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.

장단점

장점

1. 시간 복잡도가 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.

2. 추가 메모리 공간을 필요로 하지 않는다. (퀵 정렬은 O(log n)만큼의 메모리를 필요)

단점

1. 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다.

코드

void swap(int[] a, int idx1, int idx2) {
  int temp = a[idx1]; a[idx1] = a[idx2]; a[idx2] = temp;
}

/*
!피벗 결정하는 과정에서 중간 값을 이용하려고 할 때 활용 가능
static int mid(int a, int b, int c) {
  if ( a >= b ) {
    if( b >= c)
      return b;
    else if ( a <= c )
      return a;
    else
      return c;
  }
  else if( a > c)
    return a;
  else if( b > c)
    return c;
  else
    return b;
}
*/

void quickSort(int[] a, int left, int right) {
  int pl = left;                  // 왼쪽 커서
  int pr = right;                 // 오른쪽 커서
  int x = a[(pl + pr) / 2];     // 피벗
  // ❗주의 
  // 피벗의 경우 숫자가 고정되어 있어야 하기 때문에 index값이 아닌 실제 value값이 들어가야한다.
  // Index를 넣어주고 아래 에서 a[x]와 같이 이용하면 피벗의 index위치가 바뀌는 순간 다른 결과가 나올 수 있다.

  do {
    while (a[pl] < x) pl++;
    while (a[pr] > x) pr--;
    if (pl <= pr)
      swap(a, pl++, pr--);
  } while (pl <= pr);

  if (left < pr) quickSort(a, left, pr);
  if (pl < right) quickSort(a, pl, right);
}

해당 코드에서 한가지 짚고 넘어갈 것이 있습니다. 다음 부분을 봐봅시다.

do {
  while (a[pl] < x) pl++;
  while (a[pr] > x) pr--;
  if (pl <= pr)
    swap(a, pl++, pr--);
} while (pl <= pr);

pl, pr을 비교 교환하는 과정에서 등호가 들어가 있다. 만약, 등호를 안넣어주고 진행하면 어떻게 될까?

등호를 지워주는 대신 같은 요소가 나오면 "pl과 pr이 동일한 요소 위에 있는지 매번 검사"해야 한다. 그래서 그냥 동일한 요소도 교환해주는 것이 더 나을 것입니다.

시간 복잡도

퀵 정렬의 경우 최선의 경우 리스트가 균형 잡히게 잘 나눠지는 경우에 정렬이 빠르게 이루어 질 것입니다.

반대로 최악의 경우는 리스트가 계속 불균형하게 나누어 지는 경우에 정렬이 매우 느리게 이루어질 것입니다.

최선의 경우

최악의 경우

---

Reference

• [알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog