【アルゴリズム】集計ソート【JS実装】

    :zhanhailiang   :2012-12-17

1.まず、2つの並べ替えられたテーブルを結合するアルゴリズムを導入し、1つの配列A[1...m]、p,q,rがその3つのインデックスであり、12つのサブ配列A[p...q]、A[q+1...r]はそれぞれ昇順に配列されており、サブ配列A[p...r]も昇順に配列されるように、A中の要素の位置を再配置する必要がある.これがA［p…q］とA［q＋1…r］を結合する過程である.マージアルゴリズムは,2つのポインタsとtを用いて,初期化時にそれぞれA[p]とA[q+1]を指し,空の配列B[p...r]で一時メモリとする.要素A[s]とA[t]を比較するたびに、小さな要素をBに追加し、同じならA[s]を追加します.そしてポインタを更新し、A[s]A[t]であればs++;逆にt++は,条件s=q+1またはt=r+1が成立すると終了する.1つ目の場合は配列A[t...r]の残りの要素をBに追加し、もう1つの場合は配列A[s...q]の残りの要素をBに追加する.最後に配列B[p...r]をA[p...r]とコピーする.疑似コードは次のようになります.

/*****************************************************************************
  ：merge
  ：  A[1...m]，p,q,r       ，  1<=p<=q<r<=m。    A[p...q]，A[q+1...r]      
  ：       A[p...q]，A[q+1...r]    A[1...m]
******************************************************************************/

s = p; t = q + 1; k = p;
while(s <= q && t <= r) {
    if(A[s] <= A[t]) {
        B[k] = A[s];
        s++;
    } else {
        B[k] = A[t];
        t++;
    }
    k++;
}
if(s === q + 1) {
    B[k...r] = A[t...r];
} else {
    B[k...r] = A[s...q];
}
A[p...r] = B[p...r];

2.連結ソート

/*****************************************************************************
  ：mergesort
  ：A[1...n]
  ：         A[1...n]
    mergesort(A, 1, n);
******************************************************************************/
   mergesort(A, low, high)
    if(low < high) {
        mid = parseInt((low + high) / 2);
        mergesort(A, low, mid);
        mergesort(A, mid + 1, high);
        merge(A, low, mid, high);
    }

前述の連結ソートの疑似コードにより、連結ソートのJS実装バージョンが与えられる.

function merge(arr, p, q, r) {
    var crr = [];
    var a = p, b = q + 1, k = p;
    while(a <= q && b <= r) {
        if(arr[a] <= arr[b]) {
            crr.push(arr[a]);
            a ++; 
        } else {
            crr.push(arr[b]);
            b ++; 
        }   
        k ++; 
    }   

    if(a === q + 1) {
        while(b <= r) {
            crr.push(arr[b]);
            b ++; 
        }   
    } else {
        while(a <= q) {
            crr.push(arr[a]);
            a ++; 
        }   
    }

    var i = 0, cl = crr.length;
    while(i < cl) {
        arr[p++] = crr[i++];
    }

    return arr;   
}

function mergesort(arr, low, high) {
    if(low === high) {
        return arr;
    } else if(high - low === 1) {
        if(arr[low] > arr[high]) {
            var temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
        }

        return arr;
    } else {
        var mid = parseInt((low+high)/2);
        arr = mergesort(arr, low, mid);
        arr = mergesort(arr, mid+1, high);
        return merge(arr, low, mid, high);
    }
}

//   
var test = [88, 32, 22, 32, 87, 88];
console.log(mergesort(test, 0, test.length - 1));