퀵소트 자바

1. 퀵소트 설명

퀵소트에서 가장 중요한 것은 퀵소트를 이해하는것이다.

퀵소트는 이해하기 까다로운 알고리즘이다. 무서운 마음으로 한번 보자.

 

퀵소트는 분할 정복(divide and conquer) 개념을 사용한다.

그럼 무엇이 분할이고 무엇이 정복인지 알아보자.

 

 

우선 정복 부터 알아보자.

배열 = [5,2,4,1,3]

위와 같이 정렬되지 않은 배열이 있다.

위 배열중에서 일단 하나만 내자리를 찾자. 라고 생각하자

 

일단 하나만 내자리를 찾자의 단계는 아래와 같다.

1. 가장 우측의 인덱스로 피벗을 정한다(내자리를 찾을 놈)

2. 피벗기준으로 작은놈들은 왼쪽, 큰놈들은 오른쪽!

3. 2번 수행 시 자동적으로 자기 자리 fix 왜냐? 작은놈은 왼쪽에, 큰놈은 오른쪽에 있으니깐!

 

정복 예제

1. p == pivot

2. i == loop돌면서 p와 비교할 대상

3. j == left

[5, 2, 4, 1, 3]
i            p 
l

i(5)는 p(3)보다 작은가? → 아니요 → 아무것도 하지말고 i를 오른쪽으로 한칸 당겨라

[5, 2, 4, 1, 3]
 l  i        p 

i(2)는 p(3)보다 작은가? → 네 → i를 l(left)와 바꾸고, i, l을 우측으로 한칸 이동해라

[2, 5, 4, 1, 3]
    l  i     p 

i(4)는 p(3)보다 작은가? → 아니요 → 아무것도 하지말고 i를 오른쪽으로 한칸 당겨라

[2, 5, 4, 1, 3]
    l     i  p 

i(1)는 p(3)보다 작은가? → 네 → i를 l(left)와 바꾸고, i, l을 우측으로 한칸 이동해라

[2, 1, 4, 5, 3]
       l    i,p 

i(1)는 p(3)보다 작은가? → 네 → i를 l(left)와 바꾸고, i, l을 우측으로 한칸 이동해라

 

 

i와 p가 같아졌다는 말은 비교 loop가 끝났다는 말이다.

이제 l(left)와 p을 바꾸자.

[2, 1, 3, 5, 4]
       p    i,l 

 

1차 정복이 완료된 모습이다.

피벗 3을 기준으로 왼쪽엔 작은것, 오른쪽엔 큰것이 놓여있다. 그리고 3은 자기자리를 잡았다.

 

여기서 생각을 멈춰라. 멈추고 분할을 생각해보자

도대체 무엇이 분할이란 말인가?

위의 정복 프로세스를 분할해서 다시 하겠다는 말이다.

어떻게? 피벗 기준으로 왼쪽으로 한번, 오른쪽으로 한번

 

 

분할

[2, 1, 3, 5, 4] // 3은 고정


[2, 1] // 왼쪽 배열
 i  p
 l
 
[5, 4] // 오른쪽 배열
 i  p
 l

왼쪽 배열을 위와같은 정복 프로세스를 돌리면 [1, 2] 배열이 완성되고

오른쪽 배열을 돌리면 [4, 5] 배열이 완성된다.

이렇게 하면 [1,2,3,4,5] 정렬된 배열이 완성된다.

 

분할의 핵심 개념은 정복 프로세스를 범위를 줄이며 반복한다. 즉 범위를 줄이면서 재귀적으로 정복 함수를 호출하자!

 

코드

class QuickSort {

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[b];
        arr[b] = arr[a];
        arr[a] = temp;
    }          

    public static void recursiveSearch(int[] arr, int left, int right) { // 분할
        if (left >= right) {
            return;
        }

        int pivotIndex = partition(arr, left, right);

        recursiveSearch(arr, left, pivotIndex - 1);
        recursiveSearch(arr, pivotIndex + 1, right);

    }


    public static int partition(int[] arr, int left, int right) { // 정복
        int i = left - 1;

        while (i < right) {
            ++i;
            if (arr[i] < arr[right]) {
                swap(arr, i, left);
                left++;
            }
        }

        swap(arr, left, right); // 좌랑 우랑 바꿔서 피벗은 자기자리 확정!

        return left;

    }

}