퀵정렬

퀵정렬이란

다른 정렬법에 비해 이해가 약간 어려운 정렬법이다.

알고리즘

정렬이 필요한 값들 중 중간값을 하나 잡는다. 이 값은 기준값이 되며 피벗 이라고 부른다.

3 0 1 8 2 7 5 4 9 6

예를들어 위와 같은 배치에서 2를 피벗으로 잡는다. 

다른 숫자를 잡아도 상관없다.           

피벗을 기준으로 왼쪽은 피벗보다 작은값, 오른쪽은 피벗보다 큰 값을 몰아 넣는게 포인트다.

이제 가장 왼쪽값부터 하나씩 오른쪽으로 옮겨가면서 피벗과 비교를 해서 피벗 보다 큰 값을 찾는다. 

3 0 1 8 2 7 5 4 9 6

--> 이 방향으로 탐색

8이 2보다 크므로 8이 첫번째 비교값이 된다.

다음은 가장 오른쪽 값부터 하나씩 왼쪽으로 옮겨가면서 피벗과 비교해서 피벗보다 작은 값을 찾는다.

3 0 1 8 2 7 5 4 9 6

                       <-- 이 방향으로 탐색

6가 7보다 작으므로 6가 두번째 비교값이 된다.

이제 8 과 6을 서로 바꾼다.

3 0 1 6 2 7 5 4 9 8

7의 왼쪽에는 7보다 작은값, 7의 오른쪽에는 7보다 큰값을 몰아넣는다.

그리고 왼쪽값들중에 새로운 피벗을 잡아 다시 왼쪽에는 작은값들, 오른쪽에는 큰값들을 정렬한다.

이 과정을 계속 반복한다. 

Java 코드는 다음과 같다.

public class QuickSort {

    private int[] array;
    public QuickSort(int arr[]){
        this.array = arr;
    }

    public static void main(String[] args) {

        int arr[] = {69, 10, 30, 2, 16, 8, 31, 22, 3};
        QuickSort qs = new QuickSort(arr);
        qs.quickSort(arr, 0, arr.length-1);
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }

    }

    int partition(int arr[], int left, int right)
    {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;

            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        };

        return i;
    }

    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);
    }




}