頑固なマージソートアルゴリズム

この記事はWeChatの公開アカウント「Beta Learns JAVA」から転載したもので、著者はSilently9527です。この記事を転載する場合は、Beta Learning JAVA パブリックアカウントにお問い合わせください。

序文

この記事では、マージ操作に基づいてソートを完了するアルゴリズムについて説明します。

マージソートアルゴリズムのアイデア

配列をソートするには、まず配列を 2 つの配列に分割して別々にソートし、次に結果をマージして、配列全体がソートされるまでこのプロセスを再帰的に繰り返します。これがマージソートのアルゴリズムの考え方です。

マージソートの利点は、任意の長さ N の配列をソートするのに必要な時間が NlogN に比例することを保証できることです。これはプライマリソートでは実現できない利点です。

欠点は、マージ操作では追加の配列の導入が必要となり、追加のスペースが N に比例することです。

インプレースマージの実装

マージソートを実装する前に、2 つの順序付き配列のマージ操作を完了する必要があります。つまり、2 つの順序付き配列を 1 つの順序付き配列にマージする必要があります。

このプロセスでは、補助配列を導入する必要があります。
定義されているメソッドシグネチャは merge(a, lo, mid, hi) です。このメソッドは、配列 a[lo..mid] と a[mid..hi] を順序付けられた配列にマージし、その結果を a[lo..mid] に格納します。
このメソッドでは、前回の記事で説明したパブリック関数をあまり使用する必要はありません。前回の記事「一般的なプライマリソートアルゴリズム、今回はすべて理解する」を参照してください。

パブリッククラス MergeSort は SortTemplate を実装します {
    プライベートComparable[] aux; 
 
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
        //実装予定
    } 
 
    プライベートvoidマージ(比較可能[] a、 int lo、 int mid、 int hi) {
 ( int i = lo; i <= hi; i++) {
            補助[i] = a[i];
        }
 int i = lo、j = mid + 1;
 ( int k = lo; k <= hi; k++) {
            もし（i＞中間）{
                a[k] = aux[j++];
            }そうでなければ (j > hi) {
                a[k] = aux[i++];
            } そうでない場合 (aux[i], aux[j]) {
                a[k] = aux[i++];
            }それ以外{
                a[k] = aux[j++];
            }
        }
    } 
 
 }

トップダウンマージソート

分割統治の考え方に基づいて、大きな配列は、最初に小さな配列に再帰的に分割し、小さな配列が整然と並んでいることを確認してから、配列全体が整然と並ぶまでそれらをマージすることによってソートされます。この操作は、トップダウンマージソートと呼ばれます。

パブリッククラス MergeSort は SortTemplate を実装します {
    プライベートComparable[] aux; 
 
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
        aux = 新しいComparable[配列.長さ];
        doSort(配列、0、配列の長さ - 1);
    } 
 
    プライベートvoid doSort(Comparable[]配列、 int lo、 int hi) {
        （最低 >= 最高）の場合{
戻る;
        }
 int mid = (hi - lo) / 2 + lo;
        doSort(配列、lo、mid);
        doSort(配列、mid + 1、hi);
        マージ(配列、lo、mid、hi);
    } 
 
    プライベートvoidマージ(比較可能[] a、 int lo、 int mid、 int hi) {
        //省略
    } 
 
 }

上記のコードは標準的な再帰マージソート操作ですが、慎重に検討すればアルゴリズムを最適化できます。

「配列がすでに順序付けられているかどうかをテストする」; a[mid]<=a[mid+1]の場合、マージメソッドをスキップしてマージ操作を減らすことができます。修復後のdoSortメソッド

プライベートvoid doSort(Comparable[]配列、 int lo、 int hi) {
    （最低 >= 最高）の場合{
戻る;
    }
 int mid = (hi - lo) / 2 + lo;
    doSort(配列、lo、mid);
    doSort(配列、mid + 1、hi);
    配列[mid].compareTo(配列[mid + 1]) >= 0の場合{
        マージ(配列、lo、mid、hi);
    }
 }

「小さな配列の場合は、挿入ソートを使用できます」。小さな配列にマージソートを使用すると再帰呼び出しスタックが増加するため、サブ配列のソートを処理するために挿入ソートを使用することを検討できます。

プライベートvoid doSort(Comparable[]配列、 int lo、 int hi) {
    （最低 >= 最高）の場合{
戻る;
    } 
 
    if (hi - lo < 5) { //テスト、5未満の場合、挿入ソートを使用する
        挿入ソート(配列、lo、hi);
戻る;
    } 
 
 int mid = (hi - lo) / 2 + lo;
    doSort(配列、lo、mid);
    doSort(配列、mid + 1、hi);
    if (less(配列[mid + 1], 配列[mid])) {
        マージ(配列、lo、mid、hi);
    }
 } 
 
 // ソートを挿入
プライベートvoid挿入ソート(比較可能な配列[]、 int lo、 int hi) {
 ( int i = lo; i <= hi; i++) {
 for ( int j = i; j > lo && less(array[j], array[j - 1]); j --) {  
            exch(配列、j、j - 1);
        }
    }
 }

「補助配列に要素をコピーする時間を節約する」; この操作を実装するのはより面倒であり、再帰の各レベルで入力データと出力配列の役割を交換する必要があります。変更後の完全なコードは次のとおりです。

パブリッククラス MergeSort は SortTemplate を実装します {
    プライベートComparable[] aux; 
 
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
        aux = 配列.clone();
        doSort(aux, 配列, 0, 配列の長さ - 1);
    } 
 
    プライベートvoid doSort(Comparable[] src、Comparable[] dest、 int lo、 int hi) {
        （最低 >= 最高）の場合{
戻る;
        } 
 
        if (hi - lo < 5) { //テスト、5未満の場合、挿入ソートを使用する
            挿入ソート(dest, lo, hi);
戻る;
        } 
 
 int mid = (hi - lo) / 2 + lo;
        doSort(dest, src, lo, mid);
        doSort(dest, src, mid + 1, hi);
        if (less(src[mid + 1], src[mid])) {
            マージ(src、dest、lo、mid、hi);
        }
    } 
 
    // ソートを挿入
    プライベートvoid挿入ソート(比較可能な配列[]、 int lo、 int hi) {
 ( int i = lo; i <= hi; i++) {
 for ( int j = i; j > lo && less(array[j], array[j - 1]); j --) {  
                exch(配列、j、j - 1);
            }
        }
    } 
 
    プライベートvoidマージ(Comparable[] src、Comparable[] dest、 int lo、 int mid、 int hi) {
 int i = lo、j = mid + 1;
 ( int k = lo; k <= hi; k++) {
            もし（i＞中間）{
                dest[k] = src[j++];
            }そうでなければ (j > hi) {
                dest[k] = src[i++];
            }そうでない場合 (less(src[i], src[j])) {
                dest[k] = src[i++];
            }それ以外{
                dest[k] = src[j++];
            }
        }
    } 
 
 }

再帰操作の各層はサブ配列をソートしますが、サブ配列はaux[lo..hi]またはa[lo..hi]である可能性があります。doSortの最初の呼び出しではsrc = auxとdest = arrayが渡されるため、再帰の最終結果は配列に入力され、配列全体のソートが完了していることを確認する必要があります。

ボトムアップマージソート

マージアルゴリズムを実装する別の方法は、最初に小さな配列をマージし、次に配列全体が順序付けられるまでサブ配列をペアでマージすることです。

パブリッククラス MergeSort は SortTemplate を実装します {
    プライベートComparable[] aux; 
 
    @オーバーライド
パブリックvoid ソート(比較可能な[] 配列) {
 int長さ = 配列.長さ;
        aux = 新しいComparable[長さ];
 ( int sz = 1 ; sz < 長さ; sz += sz) {
 ( int i = 0; i < 長さ - sz; i += 2 * sz) {
                merge(配列、i、i + sz - 1、 Math.min (i + 2 * sz - 1、長さ - 1));
            }
        }
    } 
 
    プライベートvoidマージ(比較可能[] a、 int lo、 int mid、 int hi) {
 ( int i = lo; i <= hi; i++) {
            補助[i] = a[i];
        }
 int i = lo、j = mid + 1;
 ( int k = lo; k <= hi; k++) {
            もし（i＞中間）{
                a[k] = aux[j++];
            }そうでなければ (j > hi) {
                a[k] = aux[i++];
            } そうでない場合 (aux[i], aux[j]) {
                a[k] = aux[i++];
            }それ以外{
                a[k] = aux[j++];
            }
        }
    } 
 
 }