선형 시간 분할하기

퀵 정렬에서 중요한 부분은 하위 배열 array[p..r]을 하위 배열에서 얻은 피벗값을 중심으로 파티션을 나누는 분할 단계입니다. 하위 배열 내 어떤 요소이든 피벗으로 고를 수는 있지만 하위 배열에서 가장 오른쪽 요소 A[r]을 피벗값으로 고르면 파티셔닝을 구현하기가 쉽습니다.

피벗값을 선택하게 되면 하위 배열 각각의 요소를 왼쪽에서 오른쪽으로 피벗과 비교해 나감으로써 하위 배열을 분할합니다. 두 개의 인덱스 q와 j를 갖고 하위 배열을 4개 그룹으로 나눕니다. 변수 이름 q를 사용하는 이유는 인덱스가 결국 피벗값을 가리키게 되기 때문이고 j를 사용하는 이유는 j가 일반적으로 쓰는 카운터 변수 이름이고 끝나면 버려지기 때문입니다.

처음에는 q와 j 값이 p와 같습니다. 각 단계에서는 그룹 U의 가장 왼쪽 항목인 A[j]와 피벗값을 비교합니다. A[j]가 피벗값보다 크면 j값을 하나 증가시켜 그룹 G와 U를 나누는 선을 오른쪽으로 한 칸 밀어냅니다.

A[j]가 피벗값보다 작거나 같으면 A[j]와 A[q](그룹 G에서 가장 왼쪽 항목) 를 바꾸고 j 와 q를 하나 증가시킵니다. 그러면 그룹 L과 G를 나누는 라인과 그룹 G와 U를 나누는 라인을 오른쪽으로 한칸 밀어내게 됩니다:

피벗까지 가면 그룹 U는 비게 됩니다. 피벗을 그룹 G의 가장 왼쪽 요소와 바꿉니다: A[r]과 A[q]를 바꿉니다. 이렇게 바꾸면 피봇이 그룹 L과 G 사이에 놓이게 되는데 이는 그룹 L이나 그룹 G가 비어있을 경우에도 해당됩니다. (그룹 L이 비어있는 경우 q 값은 초기값 p에서 전혀 증가하지 않기 때문에 피벗값은 하위 배열에서 가장 왼쪽으로 이동하게 됩니다. 그룹 G가 비어있는 경우 q는 j가 증가할 때마다 증가하게 되며 j가 피벗의 인덱스인 r값에 다다르게 되면q는 r과 같아지고 바꾸기 과정에 의해 피벗은 하위 배열의 가장 오른쪽 위치하게 됩니다.) 이런 개념을 구현한 partition 함수가 피벗을 놓아야 할 인덱스 q를 반환해 이를 호출한 quicksort 함수에서 파티션이 어디에서 이루어지는지 알 수 있어야 합니다. 아래 그림에서는 array[4..9]에 해당하는 하위 배열 [12, 7, 14, 9, 10, 11]에서 파티셔닝이 이루어지는 과정을 나타냈습니다.

$n$‍ 개 요소를 가진 하위 배열의 파티션을 나누는 데는 $\mathrm{\Theta }(n)$‍ 시간이 걸립니다. 각 요소 A[j]는 한 번씩 피벗값과 비교됩니다. A[j]는 A[q]와 자리를 바꾸거나 바꾸지 않을 수 있고 q도 증가되거나 증가되지 않을 수 있습니다. j는 항상 증가됩니다. 하위 배열의 한 요소당 실행되는 총 코드 줄의 수는 상수입니다. 하위 배열에는 $n$‍개 요소가 있으므로 파티션을 나누는데 드는 시간은 선형적 시간:$\mathrm{\Theta }(n)$‍입니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.