퀵솔트(Quick Sort)

이름부터 빨라보이는 정렬 알고리즘 퀵솔트이다

이 알고리즘을 이해하는데 시간이 굉장히 걸렸다

알고리즘의 시간복잡도는 O(n log n)이 나오게 되는데
최악의 경우 n^2이 나오게된다
하지만 평균적으로 n log n이 나온다는것을 기억하자

그 이유는 전화번호부에서 사람을 찾는 알고리즘을 알고있으면 그것과 비슷하기 때문이다.

---

전화번호부에서 "박은빈"을 찾으려면 ㅂ으로 시작하는 페이지를 찾아야한다
그러기위해서 하나하나 찾을 수 있지만 너무 오래걸리기때문에
책의 절반 페이지를 편다 (1000쪽이라면 500쪽)
그리고 그 위치에 있는 한글을 살펴본다

만약 ㅈ이라하면 ㅂ은 ㅈ보다 앞에있기때문에 시작부분과 ㅈ의 절반 페이지를 편다

그렇게 나온페이지가 ㅁ이면 ㅂ은 ㅁ보다 뒤에 있기때문에 ㅁ부터 ㅈ까지의 페이지의 절반 페이지를 편다

그러면 ㅅ이 나오게되고 ㅅ은 ㅂ보다 앞에있기때문에 ㅁ과 ㅅ의 절반의 페이지를 펴게되면 ㅂ이 나오게 된다

그런다음 여기서 같은 함수를 이용해 반복하면 "박은빈"을 찾을 수 있다

하나하나 찾는 수보다 정말 빠른 방법으로 이름을 찾을 수있다

---

그래서 지금부터 내 방식대로 여기에 적어보고 코드를 작성해보겠다

과정

[0]	[1]	[2]	[3]	[4]	[5]	[6]
3	9	1	6	10	2	7

위와같은 배열이 있다고 가정하자
퀵솔트를 사용하기위해서는 "pivot"이라는 기준을 정하는게 중요하다
기준은 여러가지 종류로 사용 될 수있는데
제일 많이 사용하는 기준은 배열의 시작, 배열의 중간, 배열의 끝이다

그래서 나는 배열의 중간을 기준으로 만들었다

그 다음에 정렬을 해주어야하는데 정렬 대신에 pivot을 기준으로
pivot보다 작은값은 pivot앞으로, pivot보다 큰 값은 pivot뒤로 보내버린다

위의 과정을 실행하기 위해 배열의 위치를 나타내는 left과 right를 만들것이다
그리고 left는 배열의 시작부터, right는 배열의 끝부터 한칸씩 이동을 한다

여기서 left중에 pivot보다 작은값이 있으면 그냥 지나치고 pivot보다 큰 값이 나오면 그 자리에서 대기를 한다
그 후 right를 돌며 pivot보다 큰 값이 있으면 지나치고 pivot보다 작은 값이 나오면
그 자리에서 멈춘뒤 left와 right를 서로 바꿔주고 한칸씩 이동한다

[0]	[1]	[2]	[3]	[4]	[5]	[6]
3	9	1	"6"	10	2	7
L						R

(각 배열의 끝에서 시작 pivot은 배열의 중간에 위치한 6이다)

[0]	[1]	[2]	[3]	[4]	[5]	[6]
3	9	1	"6"	10	2	7
	L					R

(left에서 pivot보다 큰 값이 나왔으므로 대기)

[0]	[1]	[2]	[3]	[4]	[5]	[6]
3	9	1	"6"	10	2	7
	L				R

(right에서 pivot보다 작은 값이 나왔으므로 대기)

[0]	[1]	[2]	[3]	[4]	[5]	[6]
3	2	1	"6"	10	9	7
		L		R

(두 수를 바꾼다음 한칸씩 이동시킨다)
(그리고 [2]와 [4]는 pivot보다 작거나 크기때문에 그냥 이동한다)

[0]	[1]	[2]	[3]	[4]	[5]	[6]
3	2	1	"6"	10	9	7
		R		L

(right가 left보다 커졌을경우 종료한다)

이렇게 될 경우 6의 위치는 확정적으로 정해지게되었다

그 다음 배열을 두개로 쪼개서 같은 함수를 반복시킨다

[0]	[1]	[2]	[3]
3	"2"	1	6
L			R

(왼쪽 배열에서 다시 left와 right를 시작한다)
(pivot은 2가되고 3은 2보다 크고 6은 2보다 크기때문에 한칸이동한다)
(그 다음 1은 2보다 작기때문에 서로 바꿔주고 이동시킨다)

[0]	[1]	[2]	[3]
1	"2"	3	6
R		L

(right보다 left가 커졌으므로 함수 종료 여기서 배열의 반을 나눠서 다시 함수를 실행시킨다)

[0]
1
LR

(왼쪽 배열은 1밖에 없기때문에 바로 함수가 종료되고 1의 위치를 리턴한다)

[1]	[2]
2	"3"
L	R

(오른쪽 배열의 pivot은 3이되고 left가 한칸 이동하게 된다)

[1]	[2]
2	"3"
	LR

(L과R이 같은 위치에 있기때문에 함수 종료하고 다시 배열을 반으로 나눈다.)
(이렇게 되면 각 배열에 들어있는 수는 1개밖에 없기때문에 배열의 위치를 리턴받는다)

[4]	[5]	[6]
10	"9"	7
L		R

오른쪽 배열도 같은 함수를 이용해 정렬시킨다

[4]	[5]	[6]
10	"9"	7
L		R

(pivot보다 크므로 대기한다 그리고 두 수를 바꿔주로 한칸 이동한다)

[4]	[5]	[6]
7	"9"	10
	LR

(함수가 끝나게되고 다시 배열을 반으로 나눈다)

[5]	[6]
9	"10"
L	R

(여기 역시 함수가 바로 끝나도 배열이 2개로 나뉜다음 배열의 위치를 리턴받는다)

그렇게 모든 정렬이 완료되면 재귀형으로 하나씩 올라가며 리턴받은 배열들을 합쳐서 정렬된 배열이 완성된다

[0]	[1]	[2]	[3]	[4]	[5]	[6]
1	2	3	6	7	9	10

코드

public class QuickSort3 {

    int[] solution(int[] arr) {
        //정렬하기위한 배열과 left, right값 전달
        return quickSort(arr, 0, arr.length-1);
    }

    //재귀함수로 동작하게 된다
    int[] quickSort(int[] arr, int left, int right) {

        //1. 먼저 part를 구하기 위해 partition함수를 실햄한다
        int part = partition(arr, left, right);

        //9. left의 위치를 반환받아 part에 넣게되면 배열을 반으로 쪼갠 위치가 나오게된다
        //여기서 left가 part-1보다 작을때까지 계속 실행시켜주는데
        //배열이 한개일경우 part가 1이되게되고 part-1은 0이어서 정렬할 필요가 없기 때문이다
        if(left < part-1) {
            //10. 재귀를 이용해 왼쪽 배열들을 정렬시켜준다.
            //왼쪽 배열이기때문에 배열의 오른쪽이 part-1이 되었다
            quickSort(arr, left, part-1);
        }
        if(part < right) {
            //11. 재귀를 이용해 오른쪽 배열들을 정렬시켜준다
            //오른쪽 배열이기때문에 배열의 왼쪽이 part가 되었다
            quickSort(arr, part, right);
        }

        return arr;
    }

    int partition(int[] arr, int left, int right) {
        //2. partition함수에서 왼쪽과 오른쪽의 합을 나누어 중간값 pivot을 구한다
        int pivot = arr[(left+right)/2];

        //3. left가 right보다 커지거나 같아질때까지 반복문을 돌린다
        while(left <= right) {
            //4. left에 위치한 배열의 값이 pivot보다 작을경우 패스한다
            //5. right에 위치한 배여의 값이 pivot보다 클경우 패스한다
            //이렇게되면 left에서 pivot보다 큰 값이 나올경우 while문이 멈추어서 그 값을 유지한다
            while (arr[left] < pivot) left++;
            while (arr[right] > pivot) right--;

            //6. left가 right보다 작거나 같을때 서로 두 수를 바꿔준다
            //7. 그리고 left와 right를 한칸씩 이동시켜준다
            if (left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }

            //이 코드를 left가 right보다 작거나 갈을때까지 반복시킨다
        }
        //8. 그리고 left의 위치를 반환시키게 된다
        return left;
    }

    //값을 서로 바꿔주는 메서드
    void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    public static void main(String[] args) {
        QuickSort3 quickSort3 = new QuickSort3();

        int[] arr = {3,9,1,6,10,2,7};

        int[] result = quickSort3.solution(arr);

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