개요

1959년 영국의 컴퓨터 과학자 Sir Antony Hoare가 고안한 정렬 알고리즘.

  • TAOCP

빠른정렬을 다른 방식들과 결합한다면 빠른 평균 실행 시간뿐만 아니라 최악의 경우에서의 규모의 정렬 시간을 절대적으로 보장할 수 있다. 1

  • CLRS

퀵 정렬은 원소 수가 n개인 입력 배열을 최악의 경우 에 정렬하는 알고리즘이다. 퀵 정렬은 최악의 경우에는 수행시간이 느리지만 평균 수행시간이 으로 매우 효율적이고 표현에 숨겨진 상수 인자도 매우 작다. 또한 내부 정렬이라는 장점도 있고 가상 메모리 환경에서도 잘 동작해 일반적으로 실제 문제에서 가장 유용한 정렬 방법이다. 2

알고리즘

그럼 이와는 상당히 다른, 각 비교의 결과를 이용해서 다음번에 비교할 키들을 결정하는 전략을 살펴보자. 그와 같은 전략은 병렬 계산에는 부적합하지만, 직렬로 작동하는 컴퓨터에서는 상당히 이득이 된다.

여기서 말하는 방법의 기본적인 발상은 이런 것이다. 한 레코드(이를테면 )를 취하고, 그것을 정렬된 파일에서 차지해야 할 최종 위치(이를테면 )로 이동한다. 이 최종 위치를 결정하는 도중에, 위치 의 왼쪽에 현재 레코드의 키보다 더 큰 키들이 존재하지 않도록, 그리고 그 오른쪽에는 그보다 더 작은 키들이 존재하지 않도록 다른 레코드들도 적절히 재배치한다. 결국 파일은 원래의 정렬 문제가 두 개의 보다 간단한 문제들, 즉 을 각각 독립적으로 정렬하는 문제들이 되는 방식으로 분할된다. 각 부분파일들에도 마찬가지 기법을 적용한다. 그러다 보면 결국은 파일 전체가 제대로 정렬된다. 1

분할 교환 정렬 알고리즘

TAOCP에는 다음과 같은 분할 교환 정렬도 함께 소개된다.

파일을 왼쪽, 오른쪽 부분파일들로 분할하는 방법은 여러 가지가 있는데, 세지윅(R. Sedgewick)에서 기인한 다음과 같은 방법이 알고리즘을 분석하기에 좀 더 깔끔하다는 점에서 최선인 것 같다.

이 방법은 다음과 같다.

  • 수열 이 주어진다. 이 수열 을 분할하며 정렬할 것이다.
    • 분할은 왼쪽과 오른쪽 부분으로 나눈다.
  • 두 개의 포인터 i, j를 둔다.
    • 초기값은 i = 2, j = N이다.
    • 왼쪽과 오른쪽으로 나누는 기준은 가장 왼쪽 원소이다.
  • 만약 가 분할 이후에 왼쪽 부분으로 가게 된다면, i1 증가한다.
    • 이 과정을 오른쪽 부분파일에 속할 레코드 에 도달할 때까지 반복한다.
  • j는 왼쪽 부분파일에 속할 레코드 를 만날 때까지 계속 감소한다.
  • 만약 이면 와 교환한다.
  • 이 작업을 양쪽에서 가 될 때까지 반복한다.

다음은 이 작업을 수행한 예제이다.

이 예제만 봐서는 이해가 잘 가지 않는다. 그래서 한 줄 한 줄 설명을 적어 보았다.

        i                                                                     j
[ 503  087  512  061  908  170  897  275  653  426  154  509  612  677  765  703 ]
  • i = 2 이므로 . 그리고 .
    • 087503보다 작다. 왼쪽 부분이다.
    • 703503보다 크다. 오른쪽 부분이다.
    • 둘 다 교환하지 않아도 된다.
             i                                       j
[ 503  087  512  061  908  170  897  275  653  426  154  509  612  677  765  703 ]
  • i는 한 칸씩 오른쪽으로 가다가 503보다 큰 512에서 멈춘 상태.
  • j는 한 칸씩 왼쪽으로 오다가 503보다 작은 154에서 멈춘 상태.
  • 이제 512154의 위치를 바꾼다. (아래 그림의 ---)
                       i                        j
[ 503  087  154  061  908  170  897  275  653  426  512  509  612  677  765  703 ]
            ---                                     ---
  • i는 한 칸씩 오른쪽으로 가다가 503보다 큰 908에서 멈춘 상태.
  • j는 한 칸씩 왼쪽으로 오다가 503보다 작은 426에서 멈춘 상태.
  • 이제 908426은 위치를 바꾼다.
                                 i    j
[ 503  087  154  061  426  170  897  275  653  908  512  509  612  677  765  703 ]
                      ---                      ---
  • 똑같은 방법으로 i897, j275에서 멈춘 상태.
  • 897275는 위치를 바꾼다.
                                 j    i
[ 503  087  154  061  426  170  275  897  653  908  512  509  612  677  765  703 ]
                                ---  ---
  • 그리고 두 포인터 i, j는 서로 만난다(Pointer cross).
                                  j     i
[ 275  087  154  061  426  170 ] 503 [ 897  653  908  512  509  612  677  765  703 ]
  ---                            ---
  • 이제 275503을 교환한다.
  • 503은 정렬이 완료된 숫자가 된다.
  • 275 ~ 170은 왼쪽으로 분할된다.
  • 897 ~ 703은 오른쪽으로 분할된다.

이제 분할된 각 수열에 대해 같은 과정을 반복하면 된다.

이 방법은 호어(C. A. R. Hoare)3에서 기인한 것으로, 그의 흥미로운 논문은 지금까지 출판된 것들 중 하나의 정렬 방법에 대해 가장 상세한 설명을 담은 논문에 속한다고 할 수 있다. 호어는 그의 방법을 "빠른정렬(quicksort)"이라고 불렀는데, 그 이름은 과장이 아니다. 계산의 내부 루프들이 대부분의 컴퓨터에서 극도로 빠르기 때문이다. 한 주어진 시기에서 일어나는 모든 비교는 같은 키에 대한 것이므로, 이 키를 하나의 레지스터 안에 담아둘 수 있다. 비교들 사이에서는 색인 하나만 바꾸면 된다. 게다가 자료 이동 횟수도 상당히 적당하다. 예를 들어 표2의 경우 교환 횟수는 단 17이다.

i와 j, 그리고 스택을 제어하는 데 필요한 관리 작업이 어려운 것은 아니나, 그래도 그 작업 부담 때문에 빠른정렬의 분할 절차는 N이 상당히 클 때 가장 적합하다. 1

성능

퀵-정렬의 내부 루프(분할 메서드에 있는)는 인덱스를 증가시켜가며 어떤 고정된 값과 배열 항목의 값을 비교한다. 이러한 단순함이 퀵-정렬을 빠르게 하는 요인 중 하나이다. 정렬 알고리즘으로서, 이보다 더 짧은 내부 루프를 고안하기는 어렵다. 예를 들어 [[merge-sort]]{병합 정렬}이나 [[shell-sort]]{셸-정렬}이 전형적으로 더 느린 이유는 내부 루프에서 데이터 이동까지 하기 때문이다.

퀵-정렬을 빠르게 하는 두 번째 요인은 적은 수의 비교 연산을 하기 때문이다. 퀵-정렬의 효율은 종국적으로 배열을 얼마나 잘 분할 하느냐에 달려 있다. 그리고 이 부분은 어떤 항목을 분할 기준 항목으로 선택하느냐에 달려 있다. 그리고 이 부분은 어떤 항목을 분할 기준 항목으로 선택하느냐에 의해 결정된다. 4

  • 퀵-정렬의 효율은 배열을 얼마나 잘 분할하느냐에 달려 있다.

최악의 경우

퀵 정렬에서 최악의 경우는 분할과정에서 원래의 문제를 n-1 개 짜리와 0개 짜리 부분 문제로 나누는 때다. 5

결론을 먼저 말하자면 최악의 경우 수행 시간은 이다.

그러므로 퀵 정렬의 최악의 경우 수행시간은 고작해야 삽입 정렬 수준이다. 게다가 이라는 수행시간은 입력 배열이 거의 완전히 정렬되어 있을 때 일어나는데, 삽입 정렬을 이용하면 오히려 대부분의 경우에 시간에 정렬이 가능한다. 5

최악의 경우만 계속해서 발생하는 상황을 재귀 관계식으로 나타내면 다음과 같다.

  • 분할에 소요되는 시간은 .
    • 분할하려면 n개의 배열 인덱스를 다 돌아야 한다.
  • .
    • 길이가 0 인 배열을 정렬하는 데에는 상수 시간이 걸린다.

이 재귀식은 어렵지 않게 이라는 것을 알 수 있는데 그냥 다음과 같은 덧셈이기 때문이다.

재귀식을 고지식하게 풀면 다음과 같이 될 것이다.

최선의 경우

가장 고른 분할은 PARTITION이 생성하는 부분 문제 두 개의 크기가 각각 이 되어 양쪽 모두 크기가 이하인 경우다. 이 경우 퀵 정렬이 아주 빠르게 동작한다. 상한과 하한 함수, -1 과 같은 상수항을 무시한다면 수행시간에 대한 재귀 관계식은 다음이 된다.

마스터 정리(정리 4.1)의 두 번째 경우에 따라 이 식의 해는 이다. 따라서 재귀 호출을 할 때마다 항상 분할이 균등하게 이루어진다면 알고리즘도 (점근적으로) 빠르게 동작한다. 5

마스터 정리 적용

위의 인용문에서 사용한 마스터 정리는 다음과 같다.

이 점화식의 해는 이다. 6

그냥 외운 답을 말하고 끝난 것 같아 싱겁다.

큰 차이는 없지만 [[master-theorem]]에 정리된 일반형 마스터 정리 도 사용해 보자.

이므로, a, b… 등의 값은 다음과 같다.

  • , , , .
  • .
    • 그러므로 이고, 이다. 마스터 정리 2-a를 사용할 수 있다.

마스터 정리 2-a는 다음과 같다.

각 값을 대입해 보면 다음과 같이 된다.

함께 읽기

  • [[master-theorem]]
  • [[merge-sort]]
  • [[shell-sort]]

참고문헌

  • [CLRS] Introduction to Algorithms 3판 / 토머스 코멘, 찰스 레이서손, 로날드 리베스트, 클리포드 스타인 공저 / 문병로, 심규석, 이충세 공역 / 한빛아카데미 / 2014년 06월 30일
  • [KNU] The art of computer programming 3 정렬과 검색(개정2판) / 도널드 커누스 저 / 한빛미디어 / 초판 2쇄 2013년 02월 10일
  • [SED] 알고리즘 [개정4판] / 로버트 세지윅, 케빈 웨인 저/권오인 역 / 길벗 / 초판발행 2018년 12월 26일

주석

  1. [KNU] 5.2.2장.  2 3

  2. [CLRS] 7장. 

  3. 퀵 정렬을 고안한 컴퓨터 과학자. 

  4. [SED] 2장. 292쪽. 

  5. [CLRS] 7.2장.  2 3

  6. [CLRS] 4장.