퀵소트 (Quick Sort)

손코딩 단골 두번째 퀵소트를 공부해야한다.

pivot과 비교해서 얠 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값으로 정렬한다.

평균 시간 복잡도는 O(n log n) 이다.

정렬 되지 않은 배열  3, 9, 4, 7, 5, 0, 1, 6, 8, 2 로 정렬을 해봅시다.

1. pivot을 정한다. 보통 배열의 가운데 값을 선택한다. pivot = 5;

2. 배열의 왼쪽과 오른쪽 끝의 인덱스를 start, end로 둔다. start = 0, end = arr.lenth -1;

3. start 인덱스의 배열 값이 pivot보다 작으면 다음 인덱스로 넘어간다. arr[start] = 3 , pivot = 5,  start++;

4.  start 인덱스의 배열값이 pivot 보다 크면 멈춘다. arr[start] = 9, pivot = 5;

5. end 인덱스의 배열 값이 pivot보다 작으면 인덱스를 멈춘다.  arr[end] = 2, pivot = 5;

6. start 와 end의 값을 swap 한다.

3, 2, 4, 7, 5, 0, 1, 6, 8, 9

7. 그 후 start 와 end의 인덱스를 하나씩 이동시킨다. start++; end--;

8. start 인덱스의 배열 값과 pivot 비교 arr[start] = 4, pivot = 5  pivot이 크므로 다음 인덱스 start++;

9.  arr[start] = 7, pivot = 5  start인덱스의 배열 값이 pivot보다 크므로 멈춘다.

10. end 인덱스의 배열 값과 pivot 비교 arr[end] = 8, pivot= 5  end값이 pivot 보다 크므로 이전 인덱스로 넘어간다. end--;

쭈우우욱 넘어가서

11. arr[end] = 1, pivot = 5 이면 end값이 pivot보다 작으므로 멈춘다.

12. start, end의 값을 swap!

3, 2, 4, 1, 5, 0, 7, 6, 8, 9

그 후 start 와 end의 인덱스를 하나씩 이동시킨다. start++; end--;

13. arr[start] = 5 이므로 pivot보다 크지 않기 때문에 멈춘다.

14. arr[end] = 0이므로 pivot 보다 작기 때문에 멈춘다.

15. start, end의 값을 swap!

3, 2, 4, 1, 0, 5, 7, 6, 8, 9

그 후 start 와 end의 인덱스를 하나씩 이동시킨다. start++; end--;

16. 앗! start 와 end의 지정 범위가 다르므로 반복문을 빠져나온다 ( start <= end)

이렇게 pivot 값 보다 작은 값은 왼쪽에 pivot보다 큰 값은 오른쪽에 정렬된 파티션이 생성된다.

3, 2, 4, 1, 0    5, 7, 6, 8, 9

17. 이 때, start가 가리키고 있는 배열의 인덱스가 두번째 파티션의 처음 인덱스가 된다.

18. 파티션의 배열이 한개인 경우까지 열심히 재귀하여 반복한다.

소스 1

public class QuickSort {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] data = { 5, 3, 8, 4, 9, 1, 6, 2, 7 };
        System.out.print("origin : ");
        print(data);
        quick_sort(data, 0, data.length - 1);
        System.out.print("result : ");
        print(data);
    }
    private static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
        
        System.out.println();
    }
    private static void quick_sort(int[] data, int l, int r) {
        // TODO Auto-generated method stub
        int left = l;
        int right = r;
        int pivot = data[(l + r) / 2];
        System.out.println("data pivot : " + pivot + " left : " + left + " right " + right);
        do {
            while (data[left] < pivot)
                left++;
            while (data[right] > pivot)
                right--;
            if (left <= right) {
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        } while (left <= right);
        if (l < right)
            quick_sort(data, l, right);
        if (r > left)
            quick_sort(data, left, r);
    }
}

소스2

public class quickSort {
    private static void qSort(int[] arr) {
        qSort(arr, 0, arr.length - 1);
    }
    private static void qSort(int[] arr, int start, int end) {
        int part2 = partition(arr, start, end);
        if (start < part2 - 1) {
            qSort(arr, start, part2 - 1);
        }
        if (part2 < end) {
            qSort(arr, start, part2);
        }
    }
    private static int partition(int[] arr, int start, int end) {
        // TODO Auto-generated method stub
        int pivot = arr[(start + end) / 2];
        while (start <= end) {
            while (arr[start] < pivot) start++;
            while (arr[end] > pivot) end--;
            if (start <= end) {
                swap(arr, start, end);
                start++;
                end--;
            }
        }
    
        return start;
    }
    private static void swap(int[] arr, int start, int end) {
        // TODO Auto-generated method stub
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
    private static void prints(int[] arr) {
        for (int data : arr)
            System.out.print(data + ", ");
        System.out.println();
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arrays = { 3, 9, 4, 7, 5, 0, 1, 6, 8, 2 };
        prints(arrays);
        qSort(arrays);
        prints(arrays);
    }
}