連結ソート

注意:https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

「集計ソート」(Merge Sort)とは?

マージソートとも呼ばれ,クイックソート(Quick Sort)などの分割征服法により実現される.安定した順序付け.
*分割征服(Divide and Conquer)法:問題を2つの小さな問題に分けてそれぞれ解決し,結果を元の問題を解決する戦略に集中する.
順序比較でソートするため、リンクリストのソートが必要な場合に有効です.

プロセス

は半分に並んでいます.

配列の長さを2で割った.

の値を比較し、ソートしてマージします.

Java Code (Ascending & Descending)

void mergeSort(int[] arr) {
    // 정렬 값들을 저장할 배열 생성
    int[] temp = new int[arr.length];
    mergeSort(arr, temp, 0, arr.length-1);
}

void mergeSort(int[] arr, int[] temp, int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2; // 중간 위치를 구한다.
        // 구한 중간 위치를 기준으로 나누어 정렬한다.
        mergeSort(arr, temp, start, mid);
        mergeSort(arr, temp, mid+1, end);
        // 정렬이 끝난 배열들을 다시 병합
        merge(arr, temp, start, mid, end);
    }
}

void merge(int[] arr, int[] temp, int start, int mid, int end) {
    // 정렬할 값들을 임시 배열에 담는다.
    for (int i=start; i<=end; i++) {
        temp[i] = arr[i];
    }
    
    int part1 = start; // 왼쪽 부분 포인터
    int part2 = mid + 1; // 오른쪽 부분 포인터
    int index = start;
    
    while (part1 <= mid && part2 <= end) {
        // part1 부분과 part2 부분을 비교하며 정렬 값을 arr에 담고 포인터를 이동한다.
        // *Ascending
        if (temp[part1] <= temp[part2]) {
        // *Descending
        if (temp[part1] >= temp[part2]) {
            arr[index] = temp[part1];
            part1++;
        } else {
            arr[index] = temp[part2];
            part2++;
        }
        index++;
        
        // 어느 한쪽 부분의 정렬이 먼저 끝날 수 있으므로 나머지 부분을 arr에 담아준다.
        for (int i=0; i<=mid-part1; i++) {
            arr[index+i] = temp[part1+i];
        }
    }
}

時間の複雑さ

最適:O(n loḡn)

最悪:O(n loḡn)

平均値:O(n loḡn)