퀵 정렬(Quicksort)은 매우 빠른 정렬 알고리즘으로서 대다수의 컴퓨터 언어가 내부적으로 채택한 알고리즘이다.

퀵 정렬은 최악의 케이스(역순으로 정렬된 배열)에서는 삽입 정렬이나 선택정렬과 성능이 비슷하지만 평균 케이스에서는 훨씬 빠르다.

퀵 정렬을 알아보기 전에 분할(partitioning)이라는 개념을 먼저 알고 가야한다.

분할

---

퀵 정렬에서 분할은 피벗( 배열로부터 임의의 수 )를 가져와 피벗보다 작은 수는 피벗의 왼쪽, 피벗보다 큰 수는 피벗의 오른쪽에 둔다.

다음 예제로 분할을 살펴보자.

위와 같은 배열이 있다.

오른쪽 값은 항상 피벗이라고 해보자. 그렇다면 위 배열에서는 피벗은 3일 것이다. 그리고 아래와 같은 두 개의 지시자를 이용해서 분할이 진행된다. 지시자 중 하나는 배열의 가장 왼쪽에, 다른 하나는 피벗을 제외한 가장 오른쪽에 배치한다.

이제 하나의 분할은 다음과 같은 단계로 진행된다.

1. 왼쪽 지시자를 한 칸씩 오른쪽으로 옮기면서 피벗과 비교한다. 이때 피벗보다 크거나 같다면 멈춘다.

2. 오른쪽 지시자를 한 칸씩 계속 왼쪽으로 옮기면서 피벗과 비교한다. 이때 피벗보다 작거나 같다면 멈춘다. 혹은 배열 맨 앞에 도달해도 멈춘다.

3. 오른쪽 지시자가 멈췄다면 둘 중 하나를 실행한다. 왼쪽 지시자가 오른쪽 지시자에 도달하거나 넘어섰다면 다음 단계로 넘어간다. 전자가 아니라면 왼쪽 지시자와 오른쪽 지시자가 가리키고 있는 값을 교환한 후 다시 1, 2, 3단계를 반복한다.

4. 왼쪽 지시자가 가리키고 있는 값과 피벗을 교환한다.
   
   

이 과정이 끝나면 피벗 왼쪽에 있는 값은 피벗보다 작고, 피벗 오른쪽에 있는 값은 피벗보다 크다.
이렇게 되면 피벗은 올바른 위치에 있다는 것을 알 수 있다.

주어진 배열로 위와 같은 단계를 적용해보자.

1단계 : 왼쪽 지시자(숫자 0)와 피벗(숫자 3)을 비교한다.

2단계 : 0은 피벗인 숫자 3보다 작다. 왼쪽 지시자를 한 칸 옮긴다.

3단계 : 왼쪽 지시자와 피벗을 비교한다. 5가 3보다 크므로 왼쪽 지시자는 멈춘다. 이제 오른쪽 지시자를 옮길 차례다.

4단계 : 오른쪽 지시자(6)와 피벗을 비교한다. 6은 피벗(3)보다 크므로 지시자를 한칸 옮긴다.

5단계 : 오른쪽 지시자와 피벗을 비교한다. 1은 피벗(3)보다 작으므로 오른쪽 지시자를 멈춘다. 두 지시자가 멈췄다. 이때 왼쪽 지시자는 오른쪽 지시자에 도달하지 못했으므로 왼쪽 지시자와 오른쪽 지시자의 값을 교환한다.

6단계 : 다시 왼쪽 지시자를 다음 칸으로 옮긴다.

7단계 : 왼쪽 지시자와 피벗을 비교한다. 2는 3보다 작으므로 왼쪽 지시자를 한칸 옮긴다. 2를 가리키던 왼쪽 지시자는 5를 가리키게 됐으니 이제 왼쪽과 오른쪽 지시자 모두 같은 값을 가리키게 됐다.

왼쪽 지시자와 피벗을 비교한다. 5가 3보다 더 크므로 왼쪽 지시자를 멈춘다. 또한 왼쪽 지시자가 오른쪽 지시자에 도달했으므로 지시자 이동을 멈춘다.

8단계 : 마지막 단계다. 왼쪽 지시자가 가리키고 있는 값과 피벗을 교환한다.

이렇게 하나의 분할이 끝났다. 위의 이미지를 보면 알 수 있듯이, 현재 피벗인 3보다 작은 수는 3의 왼쪽에, 3보다 큰 수는 3의 오른쪽에 있다. 그리고 3은 이제 올바른 위치에 있다.

분할 구현하기

---

public class SortableArray {
	
	private int[] array; 
	
	public SortableArray( int[] array ) {
		this.array = array;
	}
	
	public int partition(int leftPointer , int rightPointer) {
		
		// 항상 가장 오른쪽에 있는 값을 피벗으로 선택한다.
		// 나중에 사용할 수 있게 피벗의 인덱스를 저장한다.
		int pivotIndex = rightPointer;
		
		// 피벗 값을 저장해둔다.
		int pivot = array[pivotIndex];
		
		// 피벗 바로 왼쪽에서 오른쪽 지시자를 시작시킨다.
		rightPointer--;
		
		while(true) {
			
			// 피벗보다 크거나 같은 값을 가리킬 때까지
			// 왼쪽 지시자를 오른쪽으로 옮긴다.
			while( array[leftPointer] < pivot ) {
				leftPointer++;
			}
			
			// 피벗보다 작거나 같은 값을 가리킬 때까지
			// 오른쪽 지시자를 왼쪽으로 옮긴다.
			while ( array[rightPointer] > pivot ) {
				rightPointer--;
			}
			// 이제 왼쪽 지시자와 오른쪽 지시자 모두 이동을 멈췄다.
			// 왼쪽 지시자가 오른쪽 지시자에 도달했거나 넘어섰는지 확인한다.
			// 그렇다면 루프를 빠져 나가 이후 코드에서 피벗을 교환한다.
			if( leftPointer >= rightPointer ) {
				break;
			}	
            // 아니라면 왼쪽 지시자가 가리키는 값과
            // 오른쪽 지시자가 가리키는 값을 교환한다.
			else {
				int temp = array[leftPointer];
				array[leftPointer] = array[rightPointer];
				array[rightPointer] = temp;
				
				leftPointer++;
			}	
		}
        
		// 분할의 마지막 단계로 왼쪽 지시자의 값과 피벗을 교환한다.
		int temp = array[leftPointer];
		array[leftPointer] = array[pivotIndex];
		array[pivotIndex] = temp;
		
        // 퀵 정렬을 위해 왼쪽 지시자의 위치를 반환한다.
		return leftPointer;
	}
}

---

누구나 자료구조와 알고리즘