퀵 정렬
퀵 정렬은 분할과 재귀로 이루어진다.
아래의 단계를 따라 퀵 정렬을 시도해보자.
-
주어지는 배열을 분할한다. 분할 메소드는 피벗을 반환한다.
-
피벗의 왼쪽과 오른쪽에 있는 배열을 각각 다른 배열로 보는 것으로 1단계 2단계를 재귀함수로 반복한다. 이렇게 되면 하위 배열이 계속 분할하게 될 것이다.
-
하위 배열의 원소가 0개 혹은 1개라면 리턴한다.
위의 이미지는 [ 0, 5, 2, 1, 6, 3 ]의 배열을 한 번 분할 메소드를 통해 분할한 것이다.
(분할 메소드가 기억이 나지 않는다면 분할 포스팅을 참고하자.)
계속 진행해보자. 1단계를 수행했으니 2단계를 수행할 차례다. 2단계에 따르면 피벗의 왼쪽과 오른쪽을 각각 다른 배열로하여 1, 2단계를 수행한다고 하였다.
그럼 먼저 왼쪽에 있는 값들을 다른 배열로 보고 다시 분할을 수행한다.
0, 1, 2에 대한 분할을 진행한다면 피벗은 맨 오른쪽 값이므로 2는 피벗이다. 또한, 왼쪽 지시자는 가장 왼쪽, 오른쪽 지시자는 피벗의 한칸 왼쪽에 지정한다.
왼쪽 지시자와 피벗을 비교한다. 0은 피벗(2)보다 작으므로 왼쪽 지시자를 한 칸 옮긴다.
왼쪽 지시자와 피벗을 비교한다. 1은 피벗(2)보다 작으므로 왼쪽 지시자를 한칸 옮긴다.
왼쪽 지시자가 가리키는 위치는 현재 피벗과 동일하므로 왼쪽 지시자를 멈춘다. 왼쪽 지시자가 멈춘 후에는 오른쪽 지시자가 움직일 차례다. 오른쪽 지시자를 움직이기 시작한다. 1은 피벗(2)보다 작으므로 오른쪽 지시자를 멈춘다.
왼쪽 지시자가 오른쪽 지시자를 지나쳐 피벗에 도달했다. 피벗 자신이 교환되므로 위치는 변하지 않는다. 피벗(2)는 올바른 위치에 놓였고 방금 진행한 분할은 현재 피벗을 반환한다.
피벗의 왼쪽에는 또 다른 배열 [0, 1]이 남았다. [0, 1]의 분할을 진행해보자.
0, 1의 피벗은 1이며 왼쪽 지시자는 가장 왼쪽 값, 오른쪽 지시자는 피벗의 한칸 왼쪽에 놓이므로 둘 다 0을 가리킨다.
0과 피벗(1)을 비교한다. 0은 피벗(1)보다 작다. 왼쪽 지시자를 한 칸 옮긴다.
1와 피벗(1)을 비교한다. 1은 피벗과 같으므로 왼쪽 지시자를 멈춘다. 다음으로 오른쪽 지시자의 값(0)와 피벗(1)을 비교한다. 0은 1보다 작으므로 오른쪽 지시자는 멈춘다.
이번에도 왼쪽 지시자가 가리키는 위치는 피벗과 동일하므로 피벗의 위치는 변하지 않는다.
1도 올바른 위치에 놓였다. 이제 반환된 피벗의 왼쪽[ 1 ]을 분할할 차례지만 위에서 알렸듯이, 원소가 1 혹은 0이 남았다면 리턴한다고 했다.
이제 0, 1, 2, 3은 정렬이 완료 되었다. 위로 돌아가 3의 오른쪽 배열도 분할하여야 한다.
맨 처음 피벗이었던 3의 왼쪽 배열들이 분할을 통해 정렬되었다. 이제 3의 오른쪽 배열인 [ 6, 5 ]에 대해서 분할을 진행해보자.
지시자를 배치시킨다. 6과 피벗(5)를 비교한다. 6은 5보다 크므로 왼쪽 지시자를 멈춘다.
오른쪽 지시자의 값(6)과 피벗(5)를 비교한다. 오른쪽 지시지의 값이 더 크므로 오른쪽 지시자를 멈춘다.
끝으로 왼쪽 지시자와 오른쪽 지시자가 만나고 있으므로 왼쪽 지시자와 피벗을 교환한다.
5가 반환되었다. 5의 오른쪽에는 원소 6 하나만 남았으므로 분할을 진행하지 않고 리턴한다.
5와 6 또한 올바른 위치에 놓였다. 모든 정렬이 성공적으로 이루어졌다.
코드 구현 - 퀵 정렬
다음은 자바로 구현해본 퀵 정렬이다. QuickSort 클래스는 분할 메소드( partition() )가 위치한 SortableArray 클래스를 상속받아 작동한다.
public class QuickSort extends SortableArray{
public QuickSort( int[] array ) {
super( array );
}
public void quickSort( int leftIndex , int rightIndex ) {
// 기저 조건: 하위 배열에 원소가 0개 또는 1개일 때
if( rightIndex - leftIndex <= 0 )
return;
// 범위 내 원소들을 분할하고 피벗의 인덱스를 가져온다.
int pivotIndex = partition( leftIndex , rightIndex );
// 피벗 왼쪽에 대해 quicksort 메소드를 재귀적으로 호출한다.
quickSort( leftIndex , pivotIndex - 1 );
// 피벗 오른쪽에 대해 quicksort 메소드를 재귀적으로 호출한다.
quickSort(pivotIndex + 1 , rightIndex);
}
}
퀵 정렬의 효율성
퀵 정렬은 각 분할마다 왼쪽 지시자와 오른쪽 지시자가 서로 만날 때까지 배열의 원소들을 피벗과 비교하므로 못해도 N번 비교한다. (N은 원소의 개수이다.)
하지만 이때, 교환 횟수는 원소들이 어떻게 정렬되어 있냐에 따라 달라지는데, 가능한 모든 원소를 교환한다고 가정하면 최대 N / 2번 교환한다. 그리고 평균적인 경우 대략 원소의 절반 정도만 교환한다. 즉, 평균적인 경우 N / 4번 정도 교환한다.
종합적으로, 평균적으로 N번 비교하고 N / 4번 교환한다. 1.25N 단계가 걸리지만 빅 오 표기법으로 나타내면 O(N) 시간으로 분할을 실행한다.
한 번의 분할의 효율을 알았으니 이제 퀵 정렬 전체를 분석해보자.
각 분할에서 반환하는 피벗은 검은색 굵은 점선으로 표시 되어있다. 또한, 각 분할마다 배열의 원소가 N개일 때 약 N단계가 걸린다. 따라서 모든 분할을 수행한 배열의 크기를 합하면 총 단계 수가 나온다.
| N | N * logN | 퀵 정렬 단계 수 (대략) |
|---|---|---|
| 4 | 8 | 8 |
| 8 | 24 | 24 |
| 16 | 64 | 64 |
| 32 | 160 | 160 |
위의 표를 보면 퀵 정렬은 약 O(NlogN) 알고리즘인 것을 확인 할 수 있다.
하지만 주의해야할 점이 있다. 퀵 정렬은 최선과 평균적인 경우 O(NlogN)의 성능을 보여주지만, 최악의 경우 O(N²)이 걸린다.
그 이유는 최악의 경우(역순으로 정렬된 배열) 피벗이 오른쪽에서부터 차례로 반환되기 때문이다. 8개의 원소를 가진 배열로 표현하면 8 + 7 + 6 + 5 + 4 + 3+ 2 + 1 의 원소를 분할하므로, 총합 36번 비교한다. 이는 N + (N - 1) + (N - 2) + ... + 1 단계가 걸린다고 표현할 수도 있다.
따라서 퀵 정렬의 최악의 케이스에서 빅 오는 O(N²)이다.
최선의 경우에 가까운 경우 O(N)이 걸리는 삽입 정렬같은 정렬을 사용하는 것이 좋을 것이고, 최악에 가까운 경우에는 퀵 정렬은 삽입 정렬과 유사하여 퀵 정렬을 사용하나마나일 것이다.
하지만 대부분의 배열은 평균적인 케이스가 훨씬 많으므로 평균적인 경우에 성능이 좋은 퀵 정렬을 널리 사용한다.
