[알고리즘]퀵 정렬(Quick Sort)

퀵 정렬

• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
• 스택 필요
• 분할과 정복을 통해 자료를 정렬
• 평균 수행 시간 복잡도는 O(nlog2n), 최악의 수행 시간 복잡도는 O(n2)

Process (Ascending)

1. 배열 가운데서 하나의 원소를 고름 이렇게 고른 원소를 피벗(pivot) 이라고 함
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눔
3. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 함. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않음
4. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복

• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있음
• 정복
  • 부분 배열을 정렬
  • 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용

    public void quickSort(int[] array, int left, int right) {
        if(left >= right) return;

        // 분할 
        int pivot = partition(); 

        // 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
        quickSort(array, left, pivot-1);  // 정복(Conquer)
        quickSort(array, pivot+1, right); // 정복(Conquer)
    }

• 분할
  • 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 (피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들) 로 분할

    public int partition(int[] array, int left, int right) {
        /**
        // 최악의 경우, 개선 방법
        int mid = (left + right) / 2;
        swap(array, left, mid);
        */

        int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
        int i = left, j = right;

        while(i < j) {
            while(pivot < array[j]) {
                j--;
            }
            while(i < j && pivot >= array[i]){
                i++;
            }
            swap(array, i, j);
        }
        array[left] = array[i];
        array[i] = pivot;

        return i;
    }

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠름
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음

단점

• 불안정 정렬(Unstable Sort)
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸림