퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

퀵 정렬은 이름처럼 가장 많이 사용되고 있는 빠른 정렬 알고리즘이다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬방법이다. 퀵 정렬에는 피벗(Pivot)이 사용되는데 이 피벗은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 ’기준’을 말한다. 퀵정렬을 수행할때는 피벗을 어떻게 설정할지는 미리 명시해야하는데 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식으로 설명하겠다. (참고로 피봇을 정하는 기준에서 수행시간의 차이가 존재한다. )

 

호어 분할 방식에서는 리스트에서 첫 번째 데이터를 피벗으로 정한다. 따라서 피벗을 정한 뒤에 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그리고 그 다음 데이터와 작은 데이터를 교환한다. 이러한 과정을 통해 정렬이 수행된다.

 

1. 리스트의 첫번째 원소인 ‘54’ 을 피벗으로 정한다.
2. 이제 피벗의 왼쪽부터 피벗인 ‘54’보다 큰 수 인 ‘93’을 선택하고, 오른쪽에서 피벗인 ‘54’ 보다 작은 수 ‘20’을 선택한다.
3. 그리고 93과 20을 교체한다.
4. 다시 피벗 ‘54’을 기준으로 피벗보다 큰 데이터와 작은 데이터를 각자 찾는다. 그리고 왼쪽부터 ‘54’보다 큰 수 ‘77’ 그리고 오른쪽부터 작은수 ‘44’를 찾아 교환한다.
5. 그리고 다시 피벗 ‘54’를 기준으로 큰수와 작은 수를 찾으면 왼쪽에서부터 찾은 큰값 ‘77’과 오른쪽에서부터 찾은 작은 값 ‘31’의 위치가 서로 엇갈린 것을 알 수있다. 이렇게 두 값이 엇갈린 경우에는 작은데이터 ‘31’과 피벗인 ‘54’을 서로 변경한다.
6. 교환하면 [ 31 26 20 17 44 54 77 55 93 ] 으로 교환한 수 ‘55’을 기준으로 왼 쪽은 ‘55’보다 작고, 오른쪽은 ‘55’보다 크다는 것을 알 수 있다 . 이렇게 피벗의 왼쪽에는 작은 데이터, 오른쪽에는 피벗보다 큰 데이터를 위치하도록 하는 작업을 분할 혹은 파티션이라고 한다.
7. 이제 ‘54’를 기준으로 왼쪽 리스트 [31 26 20 17 44 ] 에 31을 피벗을 다시 수행하고, 오른쪽 리스트 [77 55 93]에서 77로 피벗을 설정해 똑같이 다시 정렬을 반복하면 된다.
8. 이때 현재 리스트의 데이터 개수가 1개인 경우일때 정렬이 종료된다.

Java Code

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5,7,9,0,3,1,6,2,4,8};

        quickSort(arr, 0, arr.length - 1);
        System.out.print("Sorted Array :" + Arrays.toString(arr));
    }
    
    public static void quickSort(int[] arr, int start, int end) {
        
        System.out.println(Arrays.toString(arr));
        //start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬 하지않고 종료
        if (start >= end) {
            return;
        }

        //모두 인덱스로 사용할 것
        int pivot = start; //피벗은 첫번째 원소
        int left = start + 1;
        int right = end;

        while (left <= right) {
            //피벗보다 큰 데이터를 찾을 때까지 반복 즉, 큰 수를 발견하면 멈춤
            while (left <= end && arr[left] <= arr[pivot]) { //피봇이 커야지 while문 동작
                left += 1;
            }
            //피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) {
                right -= 1;
            }

            //엇갈렸다면 작은 데이터와 피봇을 교체
            if (left > right) {
                swap(arr, right, pivot); //right이 작은 데이터
            } else {
                //엇갈리지 않았다면 작은 데이터와 큰 데이터 교체
                swap(arr, left, right);
            }
        }

        //분할 이후 왼쪽과 오른쪽 부분에서 각각 정렬 수행
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

참고로 [6,9,7,8]일때 6이 피봇이고 6보다 왼쪽부터 6보다 큰수는 9로 존재하지만 작은 수는 존재하지 않는다. 이때는 아무런 교체가 일어나지 않는다. 코드상에서는 피봇 6과 right 이 6으로 같은 수가 교체가된다.

또한 [9,8,7]의 경우 9보다 큰 수가 존재하지 않으나 작은수 7이 존재한다. 이때는 피봇 9과 작은수 7이 교체된다.

퀵 정렬의 시간복잡도

먼저 퀵소트는 시간복잡도가 최악, 최선의 경우가 다르다. 병합정렬처럼 정확히 반으로 나누어 정렬을 진행하지 않기때문에 최악의 경우가 존재한다. 최선의 경우 시간 복잡도는 O(N logN)이며, 최악의 시간복잡도는 선택정렬과 삽입정렬과 마찬가지로 O(N^2)이다.

 

 

1) 최선의 시간복잡도

항상 절반으로 분할될 때 최선의 시간복잡도를 가진다. 항상 절반으로 분할되어 총 길이가 1이 되되려면 총 logN번 분할하게 된다. 예를들어 만약 데이터의 개수가 8개일 경우, 중간 값이 피벗으로 선택되면 8개 → 4개, →2개 → 1개 순으로 3번에 걸쳐 데이터가 분할된다. 이는 N개의 데이터가 1개로 분할되기까지를 logN (log8 = 3)으로 표현 할 수 있다. 따라서 분할의 횟수는 logN이며 , 분할될때마다 n번의 비교 연산이 이루어지므로 최선의 경우 시간복잡도는 O(N logN)이다.

 

2) 최악의 시간 복잡도

먼저 오름차순이나 내림차순으로 이미 정렬되어 있을 때 피벗을 최솟값 혹은 최대값으로 정했을 때 최악의 시간 복잡도를 가진다. 예를들어 1,2,3,4 라는 배열이 존재하고 피벗을 1이라고 가정한다면 1은 고정이고, [2,3,4]를 정렬해야한다. 또 피벗이 2가 되고 [3,4]를 정렬해야한다. 이 경우에는 각 배열의 비교 연산 횟수가 평균 N번 발생한다. 하지만 재귀호출은 배열의 원소 수만큼 발생하므로 재귀호출의 횟수는 N으로 늘어나 N * N 최악의 경우 O(N^2)의 시간복잡도를 가지게 된다.

퀵 정렬의 공간복잡도

주어진 배열 안에서 교환을 하므로 O(N) 이다.

퀵 정렬의 특징

1. 평균적으로 가장 빠른 정렬 알고리즘이다.
2. 이미 데이터가 정렬되어 있는 경우 시간복잡도 O(N^2)로 매우 느리게 동작한다. 삽입정렬은 이미 데이터가 정렬되어 있는 경우 O(N) 으로 빠르게 동작되는 것과 반대된다.
3. 제자리 정렬 알고리즘(in-place sorting)의 하나로 배열이외의 다른 추가 메모리를 요구하지 않는다.