퀵정렬 (QuickSort)

요약

• 분할 정복을 이용하여 정렬을 수행하는 알고리즘
• 평균 O(n log n) 시간복잡도를 가짐. (최악 O(n^2)
• Merge에 비해 추가적인 공간을 필요로 하지 않음
• 피벗선택에 따라서 시간복잡도가 달라질 수 있다.
• 다른 O(n log n) 알고리즘에 비해 훨씬 빠름

 

피벗 선택을 하는 건 첫번째요소, 중간요소, 마지막요소, 랜덤으로 선택하는 방법이있다.

나는 첫번째요소를 선택하는 방법을 하겠다.

(첫번쨰 요소를 선택하는 방법은 익히면 중간요소, 마지막요소, 랜덤 방식은 자연스럽게 적용할 수 있다. 왜냐하면 그 요소와 첫번째 요소를 swap후 퀵정렬을 하면 되기 때문)

 

i = 왼쪽에서부터 오른쪽으로 이동할 애

j = 오른쪽에서부터 왼쪽으로 이동할 애

 

순서

1. 피벗을 잡는다.
2. i, j의 값 왼쪽 끝(left), 오른 쪽 끝(right)으로 초기화
3. j부터 왼쪽으로 이동하면서 피벗보다 작은 수 찾음 (엄밀히말하면 작거나 같은수)
4. i부터 오른쪽으로 이동하면서 피벗보다 큰 수 찾음
5. i와 j에 대한 값 swap
6. 2~5반복 ( i가 j보다 크거나 같아지면 탈출)
7. 탈출할 시점엔 i와 pivot을 swap함

pivot 기준으로 왼쪽엔 작은 수, 오른쪽엔 큰 수가 배치되게 된다.

 

 

퀵정렬이 빠른 이유

퀵정렬이 빠른 이유는 퀵정렬의 내부 루프는 효율적으로 작동하도록 설계되어있기 때문.

그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU캐시의 히트율이 높아지기 때문. (지역화는 메모리에서 캐시를 갖고올 때 인접한 메모리까지 다 갖고오는 것, 물리적으로 정렬할 데이터가 가까이 있어 히트율이 높아짐)

즉 매 단계에서 적어도 1개의 원소가 자기자리를 찾게 되므로 이후 정렬할 개수가 줄어듬. (빨라지게됨)

(위키 참조)

 

 

영상에서는 중간값을 선택했지만

우리는 중간값을 첫번째 index값과 swap후

첫번째 index값을 pivot으로 하여 정렬을 하자!

 

 

 

 

 

 

 

 
public class Main2 {
    
    public static int partition(int[] array, int left, int right) {
        int mid = (left + right) / 2;
        swap(array, left, mid); // 중간값으로 선택하기 위해서 left와 바꾸어주었다.
        //  최악의 경우를 면하기 위해서 중간값 선택 (그래도 최악을 반드시 피할 수 있는 건 아니다)
     
        int pivot = array[left];
        int i = left, j = right;
     
        while (i < j) {
            // 오른쪽부터 진행해야 제대로된 결과가 나온다.
            while (pivot < array[j]) {
                j--;
            }
     
            // 같아도 i++해야하는 이유는 pivot은 지나쳐야 하기 때문에
            while (i < j && pivot >= array[i]) {
                i++;
            }
            swap(array, i, j);
        }
        
        // 마지막에 피벗과 교체한다.
        array[left] = array[i];
        array[i] = pivot;
        return i;
    }
     
    public static void swap(int[] array, int a, int b) {
        int temp = array[b];
        array[b] = array[a];
        array[a] = temp;
    }
     
    public static void quicksort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
     
        int pi = partition(array, left, right);
        
        // 중간은 그대로 둔 채 
        // 왼쪽방, 오른쪽방에 대해서 quicksort한다.
        quicksort(array, left, pi - 1);
        quicksort(array, pi + 1, right);
    }
 
 
    public static void main(String[] args) {
        int[] arr = {1, 10, 2, 6, 7, 9, 3, 8, 4, 5};
        quicksort(arr, 0, arr.length - 1);
        
        for (int i : arr) {
            System.out.println(i + " ");
        }
    }
}
 

결과값

1 2 3 4 5 6 7 8 9 10

 

 

 

다른 버전 퀵정렬 소스

 
public class Main {
    public static int partition(int arr[], int left, int right) {
        // pivot을 중간 인덱스의 값으로 선택한다.
        int pivot = arr[(left + right) / 2];
 
        // left는 right보다 무조건 작아야한다.
        while(left <= right) {
            // 피벗보다 큰걸 찾아야하기 때문에, 작다면 ++ (이동)
            while((arr[left] < pivot) && (left < right))
                left++;
            // 피벗보다 작은걸 찾아야하기떄문에, 크면 -- (이동)
            while((arr[right] > pivot) && (left < right))
                right--;
            
            // 옮겼으면 ++과 --를 해준다.
            if(left <= right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
        // 오른쪽방 첫번쨰꺼 리턴
        return left;
    }
    
    public static void quickSort(int arr[], int left, int right) {
        // 오른쪽방 첫번재깞을 받아온다.
        // 중간 인덱스 번지의 값으로 싹 파티션 정렬한다.
        int pivotNewIndex = partition(arr, left, right);
        
        // 오른쪽방 첫번쨰꺼 -1 해야지
        // 왼쪽방의 끝번지가 된다.
        if(left < pivotNewIndex - 1) {
            quickSort(arr, left, pivotNewIndex - 1);
        }
        if(pivotNewIndex < right) {
            quickSort(arr, pivotNewIndex, right);
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 10, 2, 6, 7, 9, 3, 8, 4, 5};
        quickSort(arr, 0, arr.length - 1);
        
        for (int i : arr) {
            System.out.println(i + " ");
        }
    }
}