☑️ 퀵 정렬 (Quick Sort)

내가 이해한 것을 나중에 까먹고 헤맬까봐 내 언어로 정리한 글
참고한 사이트

---

개요

선택정렬, 버블정렬, 삽입정렬의 시간 복잡도는 모두 O(n^2) 이다
데이터가 10만개만 되어도 100만의 시간복잡도를 가지는 것이다 ... 최악 ㅜㅡㅜ

반면 퀵 정렬의 시간 복잡도는 O(n*logn) 이다
이런 시간 복잡도를 가질 수 있는 이유는 pivot 을 기준으로 하나의 집합을 반으로 나누고 정렬하기 때문이다

rough한 예를 들어 1 2 3 4 5 6 7 8 9 10 을 정렬한다고 했을때 그대로 정렬하면 10*10 의 시간이 들지만, 1,2,3,4,5 와 6,7,8,9,10 으로 나눠 정렬하면 5*5*2 의 시간이 들어 거의 절반으로 줄어든다 (따라서 n이 아니라 Log2 n이 된다)

pivot 값은 집합 중 임의의 요소를 잡을 수 있는데 보통 맨 앞, 맨 뒤 또는 중간 값을 잡는다. (나는 중간 값으로 잡았다)

퀵 정렬은 분할 정복 방법으로 문제를 2개로 나누고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결한다. 대개 순환 호출(재귀)를 이용해 구현한다

---

알고리즘

• 집합 안에 있는 요소 하나를 선택 (이 값이 pivot)
• pivot을 기준으로 pivot 보다 작은 요소들은 모두 pivot의 왼쪽, 큰 요소들은 모두 오른쪽으로 옮긴다 (결과적으로 두 개의 집합으로 나눠진다. 이 과정이 partitioning)
• 각각의 집합을 다시 정렬한다
  • 분할된 집합에 대해 quick sort를 순환 호출하여 정렬을 반복한다 (그 집합의 pivot을 정하고 분할하고 정렬하고를 반복)
• 개수가 1이 될 때까지 한다

---

구현

private static void QuickSort(int arr[]){
	QuickSort(int arr[], 0, arr.length-1);
} 

• main 함수에서 호출할 QuickSort 함수이다 배열만을 전달받으면 오버로딩한 QuickSort 함수를 호출한다

private static void QuickSort(int arr[], int start, int end){
	int part2= Partition(arr, start, end); // 분할
    if(start<part2-1){ //왼쪽 집합의 요소가 1개 이상일 경우 실행
    	QuickSort(arr, start, part2-1);
    }
    if(end>part2){ //오른쪽 집합의 요소가 1개 이상일 경우 실행
    	QuickSort(arr, part2, end);
    }
}

• part2는 오른쪽 집합, 즉 pivot보다 큰 값으로 이루어진 집합의 첫 번째 인덱스를 의미한다
• 집합의 개수가 1개뿐이라면 더 이상 정렬할 필요가 없으므로 2개 이상일 때만 정렬하라는 조건을 건다

private static int Partition(int arr[], int start, int end){
	int pivot=arr[(start+end)/2]; // pivot은 값, start와 end는 인덱스
    while(start<=end){ //교차하기 전까지 계속 진행
    	while(arr[start]<pivot) start++; //큰 값을 찾을 때까지
        while(arr[end]>pivot) end--; // 작은 값을 찾을 때까지
        //두 값을 swap
        if(start<=end){
        int temp= arr[start];
        arr[start]= arr[end];
        arr[end]= temp;
        start++;
        end--;
        }
    }
    return start; 
}

• start와 end가 교차하면 pivot을 기준으로 분할이 끝난 것이므로 '교차하지 않는 동안'이 조건이 된다
• 배열의 왼쪽부터 탐색하며 pivot보다 큰 값이 있는 인덱스를 찾고 배열의 오른쪽부터 탐색하며 pivot 보다 작은 값이 있는 인덱스를 찾는다
• 이 때 두 인덱스가 교차하지 않는다면 swap 한다
• swap 후에는 각각 인덱스를 하나씩 옮긴다 ➡️ 이미 분할된 것들은 이후의 반복에서 제외하기 위해

---

전체 코드

public class QuickSort {
    public static void main(String[] args) {
        int arr[]={4,5,2,1,10,6,3,8,9,7};
        QuickSort(arr);
        for (int i=0;i< arr.length;i++)
            System.out.print(arr[i]+" ");
    }
    private static void QuickSort(int[] arr){
        QuickSort(arr,0,arr.length-1);
    }
    private static void QuickSort(int[] arr,int start, int end){ //오버로딩
        int part2=Partition(arr,start,end);// 배열 넘겨서 pivot값 받아옴..?
        if(start<part2-1){
            QuickSort(arr,start,part2-1);
        }
        if(end>part2){
            QuickSort(arr,part2,end);
        }
    }
    //pivot 값을 기준으로 더 작은 것들만 있는 집단과 더 큰것들만 있는 집단을 나누는 과정이 partition임
    //두 집합으로 나누었을 때 두 번째 집합의 첫 번째 인덱스를 반환
    private static int Partition(int []arr,int start,int end){
        int pivot=arr[(start+end)/2];
        int temp;
        while(start<=end) {//i랑 j가 엇갈릴 "때까지" 그러니까 "안 엇갈리는 동안"을 조건으로 잡아야 함
            while (arr[start] < pivot) start++; //이동을 위한 증감
            while (arr[end] > pivot) end--;
            //바꾸기
            if (start <= end) {
                temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                start++; //swap 후 정렬이 끝난 것들은 빼주기 위해서
                end--; //한 개씩 증감한다
            }
        }
        return start; //pivot의 결과 인덱스, 즉 두번째 집합의 맨 첫번째 인덱스를 반환
    }
}