[알고리즘] 퀵 정렬, Quick Sort | 설계 및 분석

퀵 정렬 알고리즘이란?

  선정된 pivot값을 기준으로 배열을 나누어가면서 재귀적으로 정렬하는 알고리즘

 

알고리즘 설계 전략

  pivot을 선정한다.

  pivot 보다 작은 값은 왼쪽, 더 큰 값은 오른쪽에 배치한다.

  양쪽 배열에 대해 다시 같은 과정을 반복함으로써 최종적으로 배열을 정렬한다.

 

알고리즘 수도코드

 

void quicksort(index low, index high) {
  index pivotpoint;
  
  if(high > low) {
    partition(low, high, pivotpoint); //배열을 pivot 값을 기준으로 반으로 나눈다.
    quicksort(low, pivotpoint-1); // 왼쪽 배열에 대해 재귀적으로 정렬
    quicksort(pivotpoint+1,high); // 오른쪽 배열에 대해 재귀적으로 정렬
    }
  }

 

void partition (index low, index high, index& pivotpoint) {
  index i, j;
  keytype pivotitem;
  
  pivotitem = s[low];
  j = low;
  
  for(i=low+1 ; i<=high ; i++)
    if(s[i] < pivotitem) { //pivot 값보다 작으면 왼쪽에 배치, ①
      j++;
      exchange s[i] and s[j];
    }
  pivotpoint = j;
  exchange s[low] and s[pivotpoint]; //pivot 값보다 크면 오른쪽에 배치, ②
  }

 

partipation 함수의 동작 원리는 다음과 같다.

 

출처 : foundations of algorithms, 도경구역

 

알고리즘 성능 분석

basic operation : 배열 원소와 pivot과의 비교(위 코드 ①, ② 부분)

 

quicksort 함수와 participation 함수 각각 따로 알아보자.

 

  participation 함수 성능분석

  participation 함수에서는 pivot값과 나머지 배열 원소들 간의 비교가 이루어지므로 every-case이다.

배열 크기를 n이라고 할 때, pivot을 제외한 나머지 배열 원소들의 수는 n - 1이므로 T(n) = n - 1이다.

∴T(n) = n - 1

 

  quicksort 함수 성능분석

  quicksort 함수는 participation 함수와 달리 every-case가 아니다. best-case/worst-case가 존재한다.

그렇다면, 어떤 경우에 worst-case일까? 먼저 아래 그림의 경우를 살펴보자.

이미 배열의 값이 크기순으로 정렬된 경우

 

  위 그림처럼 배열의 값이 이미 크기순으로 정렬된 경우, 매번 정렬 결과 pivot이 배열의 맨 끝에 온다. 즉, pivot 값이 배열의 다른 원소들보다 제일 작거나 큰 경우 이런 상황이 발생하는데 이렇게 pivot이 맨 끝에 오게되면 매번 배열이 왼쪽, 오른쪽 이렇게 두 배열로 나눠지는 것이아니라, 왼쪽 혹은 오른쪽 둘 중 하나의 배열로만 나눠진다. 따라서 재귀 호출 횟수가 줄어들어 최악의 경우가 된다.

  쉽게말하면, 배열이 두 덩이로 나뉘지 않고 지속적으로 한 덩이로 나뉘는 것이 최악의 경우가 된다는 말이다. 이 말은, 매 정렬마다 생겨나는 pivot의 수가 많을수록 좋다는 뜻이기도 하다.

 

위 내용을 토대로 최악의 경우에 대한 점화식을 세워보면

w(n) = w(한 쪽 원소개수 0 개) + w(나머지 원소개수 n-1개) + participation 함수의 시간복잡도(= every-case)

          = w(0)  + w(n - 1) + n - 1

∴ w(n) = w(0) + w(n - 1) + n - 1

 

위 점화식을 일반화해보면

T(n) = T(n - 1) + n - 1

T(n - 1) = T(n - 2) + n - 2

T(n - 2) = T(n - 3) + n - 3

. . .

T(2) = T(1) + 1

T(1) = T(0) + 0

T(0) = 0

윗 식에서 아래 식을 뺀다.

 

w(n)=1 + 2 + 3 + ... n - 1 = n(n - 1)/2 ∈ Θ(n²)

∴ w(n) ∈ Θ(n²)