퀵정렬(Quick Sort)
데이터 집합 내에서 한 피벗 값(pivot value)을 고른 다음 그걸 기준으로 두 개의 부분집합으로 나눈다.
한 쪽 부분집합에는 피벗 값보다 작은 것만, 다른 부분 집합에는 큰 것만 넣는다. 더 이상 쪼갤 부분집합이 없을 때
까지 각각의부분집합에 대해 피벗/쪼개기 작업을 재귀적으로 적용한다. 그렇게 하고 나면 최종적으로 정렬된 데이
터 집합이 만들어진다.
퀵정렬의 효율
퀵정렬은 어떤 피벗 값을 고르는지에 따라 성능이 결정된다. 가장 이상적인 피벗 값 은 전체 데이터를 절반씩으로
쪼갤 수 있는 값이다. 피벗 값을 고르고 배열을 쪼갤 때마다 각 원소에 대해 상수 시간 연산을 적용해야 한다. 각
원소마다 이 작업을 몇 번씩 할까? 최선의 경우는 재귀호출이 이뤄질 때마다 부분 리스트의 크기가 절반씩으로
줄고, 부분 리스트의 크기가 1이 되면 재귀호출이 끝난다.즉 각 원소에 대해 상수 시간 연산을 하는 횟수 n, n을
1이 나올 때까지 반복해서 2로 나누는 횟수, 즉 log(n)이다. n개의 원소에 대해 log(n)번씩 연산을 수행하므로 최선
의 경우 복잡도는 O(n log(n))이다.
하지만 피벗을 잘못 고르면 어떠게 되나?
최악의 경우라면 데이터 집합의 최소값을 피벗 값으로 고를 것이고, 그러면 한쪽 부분집합은 빈 집합이고 다른 집
합에는 n-1개 (피벗 값을 제외한 나머지)가 들어간다. 그러면 재귀호출 횟수가 O(n)이고(균형 전혀 잡히지 않은
트리는 연결 리스트와 똑같아지는 것과 마찬가지), 최악의 경우 복잡도는 O(n^2)이 된다. 이는 선택 정렬이나 삽입 정렬과 마찬가지 속도다.
어떻게 구현하나?
public static void swap(int[] arr, int left, int right){ int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } public static void quickSort(int[] arr, int left, int right){ int index = partition(arr, left, right); if(left < index - 1){ // 왼쪽 파티션 정렬 quickSort(arr, left, index - 1); } if(index < right){ // 오른쪽 파티션 정렬 quickSort(arr, index, right); } } public static int partition(int[] arr, int left, int right){ int pivot = arr[(left + right)/ 2]; // 분할 기준 원소 선정 while(left <= right){ // 왼쪽 파티션 원소 가운데 오른쪽 파티션으로 옮겨야 하는 원소 탐색 while(arr[left] < pivot) left++; // 오른쪽 파티션 원소 가운데 왼쪽 파티션으로 옮겨야 하는 원소 탐색 while(arr[right] > pivot) right--; // 원소들의 자리를 바꾸고 left와 right를 이동 if(left <= right){ swap(arr, left, right); left++; right--; } } return left; } | cs |
우선, [0] ~ [6] 범위에서의 퀵소트를 합니다.
pivot을 선택하는 기준은 각자의 판단입니다. 맨 앞, 혹은 맨뒤, 중간을 선택해도 무방합니다.
저는 중간 값을 피봇으로 선택했습니다.
이제 6을 기준으로 6보다 작은 수는 6 왼쪽에, 6보다 큰 수는 6보다 오른쪽에 배치시킵니다.
코드를 따라가 보며 손으로 써보는 것이 중요합니다.
분할정복의 과정으로 6이라는 피봇을 기준으로 [0] ~ [5](이전 pivot) - 1까지의 범위를 소팅해줍니다.
pivot은 값 2가 될 것이며, 2를 기준으로 왼쪽은 2보다 작은 수, 오른쪽은 2보다 큰 수가 되게 합니다.
마찬가지로 6의 인덱스인 [5] ~ [6] 까지도 소팅해줍니다.([5] ~ [6]은 정렬되어 있기 때문에 그림상에서는 표현하지 않았습니다.)
이제는 다시 [0] ~ [1] 인덱스 범위와 [2] ~ [4] 범위를 퀵 소트 해줍니다.
그 다음 [2]와 [3] ~ [4] 인덱스 범위를 퀵 소트 해줍니다.
후에 조금 더 쉽고 자세하게 퀵소트의 과정을 다시 설명하겠습니다.
코드를 기준으로 설명을 하자면,
분할 정복할 범위에서 left, right를 양끝의 인덱스로 잡아 놓고
피봇값보다 크거나 같은 수를 만날 때까지 left를 증가시켜줍니다.
반대로 피봇값보다 작거나 같은 수를 만날 때까지 right를 감소시켜줍니다.
그리고 이 두 수를 바꾸어 주는 겁니다. 이 과정을 분할 정복하여 전체 array를 소팅해주는 것입니다.
