[Algorithm] Quick Sort (퀵 정렬)

- 퀵 정렬

 퀵 정렬은 이름대로 매우 빠른 정렬 알고리즘에 속합니다. 퀵 정렬은 최악인 경우 O(n^2), 보통인 경우 O(nLogn)의 시간 복잡도를 갖고있는 정렬 알고리즘입니다. 최악인 경우는 정렬이 완료된 상태에서 정렬을 시도하면 발생합니다. 최악인 경우가 발생하는 경우를 살펴보기에 앞서, 퀵 정렬이 어떤 방식으로 동작하는지 알아보겠습니다.

 퀵 정렬은 분할/정복 방식으로 인자들을 정렬합니다. 분할하는 방식은 Pivot 값을 기준으로 기준보다 작은 값과 큰 값을 분류하고 정렬합니다. Pivot은 정렬 인자들 중에 프로그래머가 임의로 선정한 값입니다. 저는 배열에서 가장 오른쪽에 있는 값을 Pivot으로 선정했습니다. 이렇게 말로 설명하기보다 배열이 단계별로 어떻게 변화하는지 직접 확인하며 학습해보겠습니다. 퀵 정렬을 재귀 함수로 구현한 사실에 주목해 주시기 바랍니다.

- 정렬 과정

 아래와 같은 정렬되지 않은 배열이 있다고 하겠습니다. 저는 배열을 정렬하기위한 Pivot을 가장 오른쪽에 있는 값으로 잡았습니다. 가장 오른쪽(R)에 위치한 값을 기준으로 배열을 정렬해보도록 하겠습니다. 4를 Pivot으로 잡았고 붉은색 바탕으로 Pivot을 나타냈습니다.

1)

7

5

10

1

6

2

5

8

9

4

 정렬을 시작하는 왼쪽(L) 끝과 오른쪽(R) 끝을 정했습니다. 왼쪽은 Pivot보다 큰 값이 있는지 확인하고 오른쪽은 Pivot보다 작은 값이 있는지 찾는 방식으로 진행합니다. 왼쪽에서 이동하는 위치에 -> 표시하고 왼쪽 이동이라 칭하겠습니다. 오른쪽에서 이동하는 위치에 <- 표시하고 오른쪽 이동이라고 칭하겠습니다. 왼쪽 이동(->)은 바로 Pivot보다 큰 값을 찾았기 때문에 위치를 기억하고, 오른쪽 이동(<-)에게 다음 턴을 넘겨줍니다. 오른쪽 이동은 4(R)부터 시작해서 Pivot보다 작은 값을 찾기 위해 배열을 이동합니다. 2를 찾았고 이동을 멈춥니다. 이제 7과 2의 위치를 변경합니다.

2)

7(L) ->

5

10

1

6

2  <-

5

8

9

4(R)

 7과 2을 교환한 후에 위의 방식과 마찬가지로 왼쪽 이동(->)은 Pivot보다 큰 값을 찾고 오른쪽 이동(<-)은 Pivot보다 작은 값을 탐색합니다. 5와 1의 위치를 찾았고 위치를 변경합니다.

3)

2(L)

5 ->

10

1  <-

6

7

5

8

9

4(R)

 5와 1을 교환한 후에 왼쪽 이동(->)은 큰 값을 찾고 오른쪽 이동(<-)은 작은 값을 찾습니다. 왼쪽 이동은 10을 찾았고 오른쪽 이동에게 턴을 넘깁니다. 여기서 오른쪽 이동의 위치가 왼쪽 이동 위치와 같아지는 경우가 발생합니다. 이 경우를 이해하는 것이 중요합니다. 이 경우에는 두 이동이 만난 위치를 기준으로 왼쪽은 이미 Pivot보다 작은 값들로 이루어진 상태라는 의미입니다. 마찬가지로 두 이동의 위치를 기준으로 오른쪽은 이미 Pivot보다 큰 값들로 이루어진 상태라는 의미입니다. 이 경우에는 이제 Pivot과 왼쪽 이동의 위치를 변경합니다.

4)

2(L)

1

10  <- ->

5

6

7

5

8

9

4(R)

 Pivot과 10을 교환하고 지금부터 이전 왼쪽 이동의 위치를 기준으로 배열을 둘로 나누겠습니다. 저는 먼저 왼쪽에 위치한 배열을 먼저 정렬했습니다. 왼쪽 배열을 나누는 기준은 지금 배열의 L값과 왼쪽 이동(->)을 기준으로 나누었습니다. 새로운 Pivot은 나뉜 배열의 가장 오른쪽 끝 값인 1입니다. 새로운 왼쪽 이동과 오른쪽 이동의 위치를 잡아주었습니다.

5)

2(L) ->

1(R) <-

4

5

6

7

5

8

9

10

 왼쪽 이동이 먼저 Pivot보다 큰 값을 찾았고 오른쪽 이동에게 턴을 넘깁니다. 그러면 오른쪽 이동은 왼쪽 이동과 같은 위치로 이동하고 두 이동이 만났다는 것을 판단합니다. 아까 중요하다고 말씀드렸던 부분입니다. 이런 상황이 발생하면 탐색을 중단하고 Pivot과 두 이동이 위치하고 있는 값을 교환합니다. 이동이 완료되면 다시 정렬 작업을 수행하기 위해 왼쪽 배열을 나누겠습니다. L과 왼쪽 이동(->)을 기준으로 분할하겠습니다.

6)

1(L) <- ->

2(R)

4

5

6

7

5

8

9

10

 이전 배열의 L과 왼쪽 이동(->)으로 왼쪽 배열을 나누게되면 L과 R의 위치가 같아집니다. 이 경우는 중요한 로직 중 하나인데, 정렬을 수행할 배열 인자가 1개라는 의미이기 때문에 다른 작업을 하지 않습니다. 그리고 이전 6)번 배열에서 드디어 오른쪽 배열을 나누기 시작합니다. 오른쪽 배열은 6)번 배열의 R값과 왼쪽 이동(->)을 기준으로 분할합니다.

7)

1(L)(R)

2

4

5

6

7

5

8

9

10

 6)번 배열의 R값과 왼쪽 이동(->)의 위치를 이용해 오른쪽 배열을 찾아내면 7)처럼 1개의 배열 인자만 갖고 있는 부분 배열로 분할됩니다. L과 R이 같은 위치에 있다는 사실을 통해서 판단이 가능합니다. 7)과 마찬가지로 정렬 작업을 수행하지 않고 로직을 종료합니다.

8)

1

2(L)(R)

4

5

6

7

5

8

9

10

  8)번 로직이 완료되면 이제 4)번 상황에서의 오른쪽 배열을 탐색합니다. 4)번 상황의 오른쪽은 R 위치와 왼쪽 이동(->) 위치를 사용해서 배열을 분할합니다. 아래와 같이 분할이 되고 Pivot은 10이 됩니다. 지금부터 조금 빠르게 넘어가도록 하겠습니다. 왼쪽 이동은 Pivot보다 작은 값을 찾지만 10은 전체 배열에서 가장 큰 값이기 때문에 왼쪽 이동은 L에서 시작해서 Pivot 위치까지 이동하게됩니다. 이런 경우에 탐색을 종료하고 다시 왼쪽 배열로 분할 합니다. 말씀 드렸듯이 왼쪽 배열을 분할하는 기준은 L 위치와 왼쪽 이동(->) 위치입니다.

9)

1

2

4

5(L)

6

7

5

8

9

10(R) <- ->

 새로운 왼쪽 부분 배열의 Pivot인 9도 가장 큰 값이므로 9)번과 마찬가지인 상황이 연출됩니다. 그리고 부분 배열로 분할합니다. 왼쪽부터 부분 배열을 분할하는 이유는 단순히 맨 아래의 소스 코드에서 왼쪽 부분 배열을 만드는 재귀 메서드를 먼저 호출하기 때문입니다. 만약 오른쪽부터 탐색하기를 원한다면 메서드의 위치만 변경하면 됩니다.

10)

1

2

4

5(L)

6

7

5

8

9 (R) <- ->

10

 11)번 배열도 10)번 배열과 마찬가지인 상황이 발생합니다. 이렇게 하나하나 확인하는 이유는 이후에 메서드가 종료되는 상황을 보기 위함입니다.

11)

1

2

4

5(L)

6

7

5

8(R)  <- ->

9

10

 새롭게 만들어진 부분 배열은 조금 특이한데 Pivot과 같은 크기의 수가 포함된 배열입니다. 왼쪽 이동은 큰 값을 찾는 이동이기 때문에 시작과 동시에 같은 크기의 인자를 만나고 턴을 오른쪽 이동에게 넘깁니다. 오른쪽 이동은 같거나 작은 인자를 찾는 이동이기 때문에 5를 탐색하고 두 이동은 같은 위치에 있게됩니다. 이제 왼쪽 부분 배열을 만들지만 L의 위치와 왼쪽 이동(->)위치가 같기 때문에 정렬 작업을 수행하지 않습니다. 그리고 R과 왼쪽 이동을 기준으로 오른쪽 부분 배열을 생성합니다.

12)

1

2

4

5(L) <- ->

6

7

5(R)

8

9

10

 새로운 오른쪽 부분 배열을 만들면 아래와 같은 모습입니다. 왼쪽 이동(->)은 Pivot보다 큰 값을 찾았기 때문에 오른쪽 이동(<-)에게 턴을 넘기고 오른쪽 이동은 Pivot보다 작은 값을 찾지 못해 왼쪽 이동의 위치까지 이동하게됩니다. 그리고 Pivot과 왼쪽 이동 값을 교환합니다. 왼쪽 이동의 위치에 있는 값은 Pivot보다 크기 때문입니다.

13)

1

2

4

5

6(L) <- ->

7

5(R)

8

9

10

 13)번 부분 배열을 정렬하고 왼쪽 부분 정렬을 만들려고 하지만 L과 왼쪽 이동의 위치가 같기 때문에 정렬을 수행하지 않고 아래와 같은 오른쪽 부분 배열을 만들었습니다. 부분 배열에서 왼쪽 이동과 오른쪽 이동을 수행하면 7 위치에 두 이동이 위치하게됩니다. 이제 Pivot과 왼쪽 이동 위치의 값을 변경합니다.

14)

1

2

4

5

5

7(L) <- ->

6(R)

8

9

10

 변경을 완료하면 이제 왼쪽 부분 배열과 오른쪽 부분 배열을 만들지만 인자가 1개이거나 없는 경우이기 때문에 정렬 작업을 하지 않습니다. 이제 남은 메서드들을 return 하면서 남은 부분 배열이 있는지 확인합니다. 대표적으로 9), 10), 11)번의 경우를 확인하면 오른쪽 부분 배열을 만들어야 하지만 부분 배열을 R의 위치와 왼쪽 이동의 위치로 만들면 부분 배열의 인자가 없는 상황이기 때문에 모든 메서드들이 retrun되고 정렬을 종료합니다. 그리고 아래와 같이 정렬이 완료된 배열을 확인할 수 있습니다.

15)

1

2

4

5

5

6

7

8

9

10

- 최악의 경우 O(n^2)

 퀵 정렬의 속도가 가장 느린 경우(최악의 경우)는 배열의 인자들이 모두 정렬된 상태일 경우입니다. 아래와 같은 상황에서 배열을 퀵 정렬로 정렬하면 O(n^2) 속도가 발생합니다. 10부터 1까지 모든 인자를 확인해야하기 때문입니다. 배열에서 위의 값은 배열 인자의 값이고 아래는 반복 횟수를 나타내겠습니다.

1 1

2 2

4  3

5 4

5 5

6 6

7 7

8 8

9 9

10 10

 총 55번 배열을 반복해서 탐색해야합니다. 이 경우가 어떻게 O(n^2)이 되는지 더 쉽게 보기 위해 n을 이용해서 보도록 하겠습니다.

1 1

2 2

4  3

5 4

5 5

6 6

7 7

...

...

n n

반복 횟수를 모두 더하면 n + (n-1) + (n-2) + .... + 3 + 2 + 1 이 됩니다. 이 경우를 일반항으로 나타내면 n*n-b로 나타낼수있고 b는 상수입니다. 빅 오 표현법은 최고차 항만 사용하기 때문에 O(n*n-b)는 O(n^2)이 됩니다.

- 소스 코드

import java.util.Arrays;

public class QuickSort {
	
	public void quickSort(int[] arr, int left, int right) {
		int l, r, pivot, tmp;
		
		if(left < right){
			l = left;
			r = right;
			pivot = arr[right];
			while(l <  r){
				while(arr[l] < pivot)l++;
				while(l < r && arr[r] >= pivot)r--;
				
				tmp = arr[l];
				arr[l] = arr[r];
				arr[r] = tmp;
			}
			arr[right] = arr[l];
			arr[l] = pivot;
		
			quickSort(arr, left, l-1);
			quickSort(arr, l+1, right);
		}
	}
	
	public static void main(String[] args) {
		QuickSort q = new QuickSort();
		int[] a = {7,5,10,1,6,2,5,8,9,4};
		q.quickSort(a, 0, a.length-1);
		System.out.println(Arrays.toString(a));
	}

}