4. 퀵 정렬(Quick Sort)

 
public class Main {
    public static void main(String[] args) {
 
        int[] arr = { 6, 5, 9, 8, 7, 4 };
 
        quickSort(arr, 0, arr.length - 1);
 
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    private static void quickSort(int[] arr, int start, int end) {
 
        int left = start; // 첫 번째 원소
        int right = end; // 마지막 값
 
        // pivot을 중앙 값으로 셋팅
        int pivot = arr[(left + right) / 2];
 
        do {
            while (arr[left] < pivot) { // pivot 보다 큰 값을 만나기 전까지 반복
                left++;
            }
            while (arr[right] > pivot) { // pivot 보다 작은 값을 만나기 전까지 반복
                right--;
            }
 
            if (left <= right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
 
        } while (left <= right); // 엇 갈릴 때 까지 반복
 
        // 재귀 함수
        if (start < right) {
            quickSort(arr, start, right);
 
        }
        if (end > left) {
            quickSort(arr, left, end);
        }
    }
}
 

 

퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 최악의 경우는 이미 정렬되어 있는 경우이다. 이 경우는 삽입 정렬이 빠를 수 있다.

퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

{ 6, 5, 9, 8, 7, 4 } -> 먼저 pivot 위치를 정한다.

{ 6, 5, 9, 8, 7, 4 } -> 9보다 큰 숫자를 왼쪽부터 찾고, 9보다 작은 숫자를 오른쪽부터 찾는다. 

{ 6, 5, 9, 8, 7, 4 } -> 9보다 큰 숫자를 찾지 못해서 9로 돌아오고 작은 숫자는 4입니다. 둘이 교환합니다.

{ 6, 5, 4, 8, 7, 9 } -> 4보다 큰 숫자를 왼쪽에서 찾고 4보다 큰수를 오른쪽부터 찾는다.

{ 6, 5, 4, 8, 7, 9 } -> 4보다 큰 숫자는 6이고 작은 숫자는 찾지못하여 4입니다. 둘이 교환합니다.

{ 4, 5, 6, 8, 7, 9 } -> 8보다 큰 숫자를 왼쪽부터 찾고, 8보다 작은 숫자를 오른쪽부터 찾는다. 

{ 4, 5, 6, 8, 7, 9 } -> 8보다 큰 숫자를 찾지 못해서 8로 돌아오고 작은 숫자는 7입니다. 둘이 교환합니다.

{ 4, 5, 6, 7, 8, 9 } -> 정렬