이번에는 구현 난이도는 어렵지만 정렬의 속도가 빠른 정렬 방법 중에 합병 정렬, 힙 정렬, 퀵 정렬에 대해 알아본다. 이 세가지 정렬 방법은 평균적으로 $O(nlogn)$의 시간 복잡도를 가진다.

합병 정렬 (Merge sort)

• 합병 정렬은 배열을 계속 분할해서 길이가 1이 되도록 만든 후, 인접한 부분끼리 크기를 비교하면서 정렬하며 합병하는 방식이다.
• 분할 정복 방법을 통해 구현한다.
• 퀵 소트와는 반대로 안정 정렬 방식이다.
• 시간 복잡도는 $O(nlogn)$ 이다.

* 퀵 정렬과의 차이점

• 퀵 정렬 : 우선 피벗을 통해 정렬(partition) -> 영역쪼갬(quick sort)
• 합병 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) -> 정렬(merge)

합병 정렬 예시

• 이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수가 있다.
• 합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다
• cf) 임의 접근을 통해 정렬하는 퀵 정렬에는 배열을 사용하면 좋다.
  

합병 정렬 구현

public class Main {
    // 합병 정렬
    public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
        if (left < right) { // left가 right보다 작은동안 배열이 하나가 될때 까지 반으로 나눠가며 쪼갠다.
            int mid = (left + right) / 2; // 중간 인덱스 구하기
            mergeSort(arr, tmp, left, mid); // 중간을 기준으로 왼쪽
            mergeSort(arr, tmp, mid + 1, right); // 중간을 기준으로 오른쪽
            merge(arr, tmp, left, right, mid); // 나누어진 배열 합치기
        }
    }

    public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
        int p = left; // 왼쪽 배열의 첫번째 인덱스
        int q = mid + 1; // 오른쪽 배열의 첫번째 인덱스
        int idx = p;
        // p, q 둘 중 하나는 해당 배열 범위 안에 있는 동안
        while (p <= mid || q <= right) {
            if (p <= mid && q <= right) {   // 둘 다 범위 안인 경우
                if (arr[p] <= arr[q]) { // 값 비교하여 정렬
                    tmp[idx++] = arr[p++];
                } else {
                    tmp[idx++] = arr[q++];
                }
            } else if (p <= mid && q > right) { // 왼쪽만 남은 경우 이어주기
                tmp[idx++] = arr[p++];
            } else {                            // 오른쪽만 남은 경우 이어주기
                tmp[idx++] = arr[q++];
            }
        }

        for (int i = left; i <= right; i++) {   // 정렬된 부분 데이터 arr 쪽으로 다시 저장해주기
            arr[i] = tmp[i];
        }
    }
}

---

힙 정렬(Heap sort)

• 힙 자료구조 형태의 정렬 방식이다.
• 기존의 배열을 힙으로 구조를 변경하고 루트를 반환하며 정렬을 진행한다.
• 시간 복잡도는 $O(nlogn)$ 이다.

힙 소트가 유용할 때

• 가장 크거나 가장 작은 값을 구할 때
  • 최소 힙 or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능

• 최대 k 만큼 떨어진 요소들을 정렬할 때
  • 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있음

프로세스

1. 최대 힙 구성
2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임
3. 힙의 사이즈가 1보다 크면 위 과정 반복

힙 정렬 구현

// 힙 정렬
    
    // 힙 정렬
    public static void heapSort(int[] arr) {
        // 배열을 힙으로 재구성 (마지막 부모 노드부터 maxHeap으로 구성한다)
        for(int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        // maxHeap으로 만들었으므로 root 쪽을 끝 쪽으로 보내고 나머지 부분을 다시 힙으로 만드는 과정을 반복한다. -> 오름차순 정렬
        for(int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i);
        }
    }

    public static void heapify(int[] arr, int parentIdx, int size) {
        // 자식 노드 위치
        int leftIdx = 2 * parentIdx + 1;
        int rightIdx = 2 * parentIdx + 2;
        int maxIdx = parentIdx;

        // 왼쪽 자식 노드가 크면 maxIdx 를 해당 인덱스로 교체
        if(leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
            maxIdx = leftIdx;
        }

        // 오른쪽 자식 노드가 크면 maxIdx 를 해당 인덱스로 교체
        if(rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
            maxIdx = rightIdx;
        }

        // maxIdx 가 바뀐 경우, 부모 노드가 교체되는 것을 의미한다.
        // 교체하고 또 연쇄적으로 교체가 일어날 수 있으므로 서브 트리를 검사 하도록 재귀로 호출한다.
        if(parentIdx != maxIdx) {
            swap(arr, maxIdx, parentIdx);
            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;
    }

퀵 정렬(Quick sort)

• 자바가 기본적으로 제공하는 정렬에 사용되는 정렬 방법이다.
• 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식이다.
• 분할 정복(divide and conquer) 방법 을 통해 주어진 배열을 정렬하는 방식이다.
• 기준값이 최소 또는 최대 값으로 지정되는 경우에 시간 복잡도가 $O(n^2)$ 이지만 평균적으로는 시간복잡도가 $O(nlogn)$ 이다.
• 배열 내에서 swap 연산을 하므로 공간 복잡도는 O(n)이다.

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

• 불안정 정렬(Unstable Sort) 이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

pivot 고르는 법

기준 값인 pivot을 고르는 방법엔 여러가지가 있지만 대표적으로 3가지가 있다.
1. 배열의 맨 앞 값을 pivot으로
2. 배열의 맨 뒤 값을 pivot으로
3. 임의로 3개의 값을 고르고 그 중 중간값을 pivot으로

세번째 방법은 최대나 최소 값이 pivot이 되는 경우를 방지해 worst case( $O(n^2)$ )를 피할 수 있다.

프로세스

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.
   재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다

퀵 정렬 예시

여기서 i는 처음으로 pivot보다 큰 값이고, j는 처음으로 pivot보다 작은 값이다.

퀵 정렬 구현

// 퀵 정렬
    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right) { // 만약 left가 right보다 크거나 같게 되면 멈춘다.
            return;
        }
        
        // 분할
        int pivot = partition(arr, left, right); // 피봇 값을 구한다.
        
        // 기준값 중심으로 좌우 재귀적으로 호출한다.
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        // 가장 좌측 값(배열의 가장 앞쪽 값)을 기준값으로 설정하는 경우
        int pivot = arr[left];
        int i = left;
        int j = right;

        while(i < j) {
            while (arr[j] > pivot && i < j) { // 처음으로 피봇 보다 작은 값을 찾아야 하므로 피봇값보다 크고 i < j인 동안은 j를 왼쪽으로 이동시킨다.
                j--;
            }

            while(arr[i] <= pivot && i < j) { // 처음으로 피봇보다 큰 값을 찾아야 하므로 피봇 값보다 작고 i < j인 동안은 i를 오른쪽으로 이동 시킨다.
                i++;
            }

            swap(arr, i, j); // i와 j의 값을 swap한다.
        }
        swap(arr, left, i); // i < j일 때까지 i,j의 값을 swap하고 나서 i=j일때 i와 left인덱스의 값인 pivot값을 swap한다.

        return i; // 피봇 값의 인덱스를 반환한다.
    }

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