합병, 힙, 퀵, 트리 정렬

합병 정렬(Merge Sort) : O(Nlogn)

배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식

힙 정렬(Heap Sort) : O(Nlogn)

힙 자료구조 형태의 정렬 방식

기존 배열을 최대 힙으로 구조 변경 후 정렬 진행

퀵 정렬(Quick Sort) : O(n^2)

임의의 기준 값(pivot)을 정하고, 그 값을 기준으로 좌우로 분할하며 정렬하는 방식

정렬 평균 시간은 굉장히 빠르지만 worst case를 기준으론 O(n^2)
-> ex) 가장 최솟값이나 최대값을 pivot으로 정한 경우

보통 pivot을 정할때 맨 왼쪽, 중앙, 앞쪽에서 한개를 뽑음
-> 하지만 임의의 세 수를 뽑아서 거기의 중앙 값을 쓴다면 worst case 피할 수 있을 것!

pivot 보다 처음으로 큰 케이스가 나오는 값 7, 피봇보다 작은 케이스가 나온 값 5
-> 그 둘의 자리를 바꿈(이 과정 여러번 진행)
-> 이후 종료되었을 때 피봇값과 바꿈

트리 정렬(Tree Sort) : O(Nlogn)

이진 탐색 트리(BST)를 만들어 정렬하는 방식
-> 만든 후 inOrder 방식으로 출력

---

합병,힙,퀵 정렬 구현

합병 정렬 구현

입력 배열을 절반으로 나눌떄(log n), 머지 연산을 각 배열의 크기인 n/2에 비례하는 시간복잡도를 가짐(n)
-> 별도의 공간을 사용할 수 없을땐 Quick Sort 사용하자

밑의 코드에서는 현재 arr에 정렬된 상태를 가져왔다고 생각하자
->ex) 2357 | 1689

public class Main {

    public static void mergeSort(int[] arr, int[] tmp, int start, int end){
        if(start < end){
            int mid = (start+end) / 2;
            mergeSort(arr, tmp, start, mid);
            mergeSort(arr,tmp,mid+1,end);
            merge(arr,tmp,start,end,mid);
        }
    }

    public static void merge(int[] arr, int[] tmp, int start, int end, int mid){
        for(int i = start; i <= end; i++){
            tmp[i] = arr[i];
        }
        int part1 = start;
        int part2 = mid + 1;
        int index = start;
        while(part1 <= mid && part2 <= end){
            if(tmp[part1] <= tmp[part2]){
                arr[index] = tmp[part1];
                part1++;
            }else{
                arr[index] = tmp[part2];
                part2++;
            }
            index++;
        }
        for(int i = 0; i <= mid-part1; i++){ // 앞쪽 배열에 남은 경우, 뒷쪽은 신경안써도됨-> 그냥 그자리에 있음
            arr[index + i] = tmp[part1 + i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {3,5,2,7,1,4,6};
        int[] tmp = new int[arr.length];
        mergeSort(arr, tmp, 0, arr.length-1);
        System.out.println("합병 정렬 : " + Arrays.toString(arr));
    }
}

힙 정렬 구현(maxHeap)

public class Main2 {

    public static void heapSort(int[] arr){
        for(int i = arr.length / 2 - 1; i >= 0; i--){
            heapify(arr, i, arr.length);
        }
        // 마쳤을때 maxHeap으론 되어있지만 정렬 상태는 아님

        for (int i = arr.length-1; i > 0 ; i--) {
            swap(arr,0,i);
            heapify(arr,0,i); // i가 size가 됨(큰 수가 맨 뒤에 간다는 점 생각)
        }
    }

    public static void heapify(int[] arr, int parentIdx, int size){
        int leftIdx = 2 * parentIdx + 1;
        int rightIdx = 2 * parentIdx + 2;
        int maxIdx = parentIdx;

        if(leftIdx < size && arr[maxIdx] < arr[leftIdx]){
            maxIdx = leftIdx;
        }

        if(rightIdx < size && arr[maxIdx] < arr[rightIdx]){
            maxIdx = rightIdx;
        }

        if(parentIdx != maxIdx){
            swap(arr,parentIdx,maxIdx);
            heapify(arr,maxIdx,size); // 이 부분 잘 이해하기!
        }
    }

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

    public static void main(String[] args) {
        int[] arr = {3,5,2,7,1,4,6};
        heapSort(arr);
        System.out.println("힙 정렬 : " + Arrays.toString(arr));
    }
}

퀵 정렬(Quick Sort)

기준값보다 작은 값을 왼쪽으로, 큰 값을 오른쪽으로 이동 시킬려고 함

start는 피봇보다 작은 값을 계속 무시하면서 지나칠것이고, end는 피봇보다 큰값을 계속 무시하면서 지나칠 것

ex)

처음 start는 9에 멈춤, end는 2에 멈춤
-> 이 둘을 스왑하고 포인터를 앞으로 한개씩 옮겨줌

이후 s는 7에 스탑, end는 1에 스탑

start는 피봇값보다 작으면 건너뛰는데 5의 경우는 그렇지 않으니 5에 스탑
-> 이후 e는 0에 스탑
-> 이 둘을 스왑한 후 포인터를 옮김
-> 이때 start와 end가 조건을 만족하지 않아 루프를 벗어남

이때 중요한것이 start가 두번째 파티션의 배열 첫번째 방이란걸 인지해야함!!!

public class Main3 {

    public static void quickSort(int[] arr, int start, int end){
        int part2 = partition(arr,start, end); // 파티션을 나눈후 오른쪽방 첫번째 값(인덱스)을 part2에 받아옴
        if(start < part2 - 1){
            // 오른쪽 파티션이 start의 바로 다음에서 시작한다면 왼쪽 파티션에 데이터가 1개라는 뜻 -> 정렬이 필요X
            // 밑의 경우는 아직 데이터가 1개 이상이라는 뜻!
            quickSort(arr,start,part2-1);
        }
        if(part2 < end){
            quickSort(arr,part2,end);
        }
    }

    public static int partition(int[] arr, int start, int end){
        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;
    }

    public static void main(String[] args) {
        int[] arr = {6,2,7,9,4,5,8};
        quickSort(arr,0,arr.length-1);
        System.out.println("퀵 정렬 " + Arrays.toString(arr));
    }
}

다른 방식(로직은 똑같음, pivot을 어디잡냐 차이)

public class Main3 {

    public static void quickSort(int[] arr, int start, int end){
        if(start >= end){
            return;
        }

        int pivot = partition(arr,start,end);
        quickSort(arr,start, pivot-1);
        quickSort(arr, pivot+1, end);
    }

    public static int partition(int[] arr, int start, int end){
        int pivot = arr[start];
        int i = start;
        int j = end;
        while(i < j){
            while(arr[j] > pivot && i < j){
                j--;
            }
            while(arr[i] <= pivot && i < j){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,start,i);

        return i;
    }

    public static void main(String[] args) {
        int[] arr = {6,2,7,9,4,5,8};
        quickSort(arr,0,arr.length-1);
        System.out.println("퀵 정렬 " + Arrays.toString(arr));
    }
}

---