マージソート

Quicksortのように、マージソートは分割と征服アルゴリズムです.これは2つの半分に入力配列を分割し、2つの半分のために自分自身を呼び出すし、2つのソート半分をマージします.merge ()関数は、2つの半分をマージする際に使用します.マージ(arr,l,m,r)はarr［l . m］とarr［m＋1 . r］がソートされ,2つのソートされたサブアレイを一つにまとめると仮定するキープロセスである.詳細は次のCの実装を参照ください.
mergesort ( arr [], l , r )
Rならば
1 .中点を見つけ、配列を2つの半分に分割します.
ミドルM = L + ( R - L )/2
( 2 )前半用のコール合併
mergemaort ( arr , l , m )を呼び出す
第3の半分の呼び出し
mergemaort ( arr , m + 1 , r )の呼び出し
ステップ2と3でソートされた2つの半分をマージします.
呼び出しのマージ( arr , l , m , r )
Wikipediaからの次の図は、完全なマージソートプロセスを示します.ダイアグラムを詳しく見ると、配列が2つの半分に再帰的に分割されることがわかります.サイズが1になると、マージプロセスが動作し、完全な配列がマージされるまで、配列のマージを開始します.
マージソートチュートリアル
推奨:最初に解決する前に“練習”を解決してください.
/*マージソート用プログラム

含める

含める
//arr []の2つのサブ配列をマージします.
//最初のサブアレイはarr [ l . m ]です
//2番目のサブアレイはarr [ m + 1 . r ]です
void merge ( int arr [], int l , int m , int r )
{ }
INI I , J , K ;
int N 1 = M - L + 1 ;
int N 2 = R - M ;

/* create temp arrays */
int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
    L[i] = arr[l + i];
for (j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];

/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
    }
    else {
        arr[k] = R[j];
        j++;
    }
    k++;
}

/* Copy the remaining elements of L[], if there
are any */
while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
}

/* Copy the remaining elements of R[], if there
are any */
while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
}

｝
/* lは左のインデックス、rは右のインデックスです
ソートするarrのサブ配列
void mergesort ( int arr [], int l , int r )
{ }
を返します.
//( l + r )/2と同じですが、
//大きなLとH
int m = l +( r - l )/2 ;

    // Sort first and second halves
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    merge(arr, l, m, r);
}

｝
/*ユーティリティ関数
/配列を出力する関数*/
void printarray ( int a [], int size )
{ }
int I ;
( i = 0 ; I < size , i++)
printf ("% d ", a [ i ]);
printf ("\n ");
｝
/*ドライバコード*/
int main ()
{ }
int arr []={ 12 , 11 , 13 , 5 , 6 , 7 }
int arrrest size = sizeof ( arr )/sizeof ( arr [ 0 ]);

printf("Given array is \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;

｝
出力
与えられた配列は
12 11 13 5 7 6
ソートされた配列は
5 6 7 7 11 12