정렬알고리즘 - Quick Sort

퀵소트란?

특정한 값(pivot)을 기준으로 해당 값의 오른쪽은 큰값, 왼쪽은 작거나 같은 값으로 정렬

일반적으로 물리적으로 중간에 있는 값을 지정한다. (배열 크기 / 2)

정렬하는 방법은 아래의 과정을 반복한다.

1. 시작의 값 (Left Pointer)과 Pivot값을 비교하여 Left > Pivot  이 나올때까지 Left Pointer++
2. 끝의 값 (Right Pointer)과 Pivot값을 비교하여 Pivot >= Right 이 나올때까지 Right Pointer--
3. Left Pointer에 있는 값과 Right Pointer에 있는 값을 바꿔준다.
4. Left Pointer > Right Pointer가 될때까지 반복한다.

위 과정을 모두 정렬이 될때까지 반복하면되는데 백번 강의 듣는거보다 코드 한번 짜니까 잘 이해가 된다.

void QuickSort(int[] arr, int start, int end) {
        if(start == end) return;

        int pivotIndex = (start + end) / 2;
        int pivot = arr[pivotIndex];

        int left = start;
        int right = end ;

        while (left < right) {
            while(arr[left] < pivot) left++;
            while(arr[right] > pivot) right--;
            swap(arr, left, right);
        }

//         재귀함수
        if (start != left && left != 0) {
            QuickSort(arr, start, left - 1);
        }

        if (end != right && left != arr.length - 1) {
            QuickSort(arr, right + 1, end);
        }

        System.out.println(Arrays.toString(arr));
    }

    void swap(int[] arr, int left, int right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }

SortPractice sp = new SortPractice();

    @Test
    public void QuickSortTest() {
        int[] arr = new int[]{0, 1, 2, 3, 4};
        int[] arr2 = new int[]{7, 4, 8, 6, 3};
        int[] arr3 = new int[]{15,6,12,7,1,13,5,18,14,2,17,4,8,11,0,3,9,10,16};
        int[] arr4 = new int[]{1,7,6,5,2,4,8,0,3};
        System.out.println("Result 1 ================");
        sp.QuickSort(arr, 0, arr.length -1);
        System.out.println("Result 2 ================");
        sp.QuickSort(arr2, 0, arr2.length -1);
        System.out.println("Result 3 ================");
        sp.QuickSort(arr3, 0, arr3.length -1);
        System.out.println("Result 4 ================");
        sp.QuickSort(arr4, 0, arr4.length -1);
    }
    
Result 1 ================
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 4]
Result 2 ================
[3, 4, 6, 7, 8]
[3, 4, 6, 7, 8]
[3, 4, 6, 7, 8]
Result 3 ================
[0, 1, 2, 7, 12, 13, 5, 18, 14, 6, 17, 4, 8, 11, 15, 3, 9, 10, 16]
[0, 1, 2, 3, 4, 5, 6, 16, 14, 13, 10, 12, 8, 11, 15, 7, 9, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
Result 4 ================
[0, 1, 2, 5, 6, 4, 8, 7, 3]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8]

코드 설명

1. 전체 배열을 받고 해당 배열을 기준으로 아래 작업들을 반복한다.

2. 배열길이 / 2 index의 값을 Pivot (기준값)으로 지정한다. (아래의 예에서는 2)

3. 처음이기 때문에 당연히 이 작업의 Range는 0 ~ 8 (배열의 끝)이다.

4. left라는 시작지점부터 시작하는 포인터와 right라는 끝지점부터 시작하는 포인터를 만든다.

INDEX	0 (left)	1	2	3	4 (Pivot)	5	6	7	8 (right)
VALUE	1	7	6	5	2	4	8	0	3

5. 각각의 포인터를 아래 조건이 성립될 때까지 Pivot으로 이동시킨다.

- left : Pivot의 값보다 left포인터의 값이 클 경우

- right: Pivot의 값보다 right포인터의 값이 작을 경우

6. 위 조건까지 이동시킨 후 left와 right의 값을 바꿔 준다.

INDEX	0	1(left)	2	3	4	5	6	7(right)	8
VALUE	1	7	6	5	2	4	8	0	3

INDEX	0	1(left)	2	3	4	5	6	7(right)	8
VALUE	1	0	6	5	2	4	8	7	3

7. 이렇게 양쪽의 값을 바꿔주는 작업을 left와 right가 만날때까지 한다. 

INDEX	0	1	2 (left, right)	3	4	5	6	7	8
VALUE	1	0	2	5	6	4	8	7	3

8. left와 right가 만난 index를 기준으로 새로운 왼쪽, 오른쪽 Range를 반복한다. (재귀함수)

Left

INDEX	0	1
VALUE	1	0

Right

INDEX	3	4	5	6	7	8
VALUE	5	6	4	8	7	3

9. 위 작업들은 Range의 요소 갯수가 1개일 경우 하지 않는다 (startIndex와 endIndex가 같을 경우)