|
マージソート
 マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。 n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースな（すなわち入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない）バリエーションも提案されているが、一般には、O(n)の追加の作業記憶領域を必要とする[1]。 （ナイーブな）クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。 アルゴリズム基本的な手順は以下の通りである。
ステップ1と2の途中（すなわち細分化するまでの部分）についてこのアルゴリズムの手順に含めず、あらかじめ局所的に整列されている多数の列が与えられるもの、とすることもある。後述する、テープをマージする手法の場合、最初のテープから主記憶を可能な限り全部使って整列できるだけ整列した部分列を、順次書き出したテープから始める。 ステップ3のマージでは、2本のデータ列の先頭同士を比べ小さい方をデータ列から取り出して出力し、残りのデータをもつ2本のデータ列に対して再帰的に同じ処理を、両方が空になるまで行う。ソートすべきデータ列が部分的に順次得られる場合、オンラインアルゴリズムとして、部分データ列をソートして後でマージするという変形も可能である。 クイックソート等と同様、完全に細分化せずにスレッショルドとして適度に大きい個数を設定し、それ以下になった時点でなんらかの「ごく少数の対象専用の高速なコードによるソート」を併用するという高速化手法がある[1]。手順として書き出すと次のようになる。
他に特殊な応用例として、外部ソートの1手法でテープ（のようなシーケンシャルアクセスメディア）に収められたデータをソートする、というものがある。最も単純な、4本のテープを2本ずつ使う「平衡2系列マージ」を例に説明する。まず元のデータから、利用可能な内部記憶をできるだけ使って、部分的に整列されている列をテープに書き出す。この時、2本のテープに交互に書き出すようにする。 次に、2本のテープのそれぞれの先頭部分にある、それぞれの部分列をマージしながら、別の2本のテープに交互に書き出す。この操作により、より長い整列した列が得られる。全てのマージが終わったら、コピー元とコピー先を入れ替え、同様に繰り返す。繰返し毎に各部分列の長さは約2倍に、列の個数は約半分になると期待できる。 最終的に、テープを切り替えることなく、1本のテープに全てのデータが出力されたら完了である。この技法はコンピュータがまだ高価で、テープが大容量外部記憶の主力だった時代にさかんに研究され、さまざまなバリエーションが編み出された。『The Art of Computer Programming』の§5.4にそれらの詳細がある。 実装例C#include <stdio.h>
void merge(int A[], int B[], int left, int mid, int right) {
int i = left;
int j = mid;
int k = 0;
int l;
while (i < mid && j < right) {
if (A[i] <= A[j]) {
B[k++] = A[i++];
} else {
B[k++] = A[j++];
}
}
if (i == mid) { /* i側のAをBに移動し尽くしたので、j側も順番にBに入れていく */
while (j < right) {
B[k++] = A[j++];
}
} else {
while (i < mid) { /* j側のAをBに移動し尽くしたので、i側も順番にBに入れていく */
B[k++] = A[i++];
}
}
for (l = 0; l < k; l++) {
A[left + l] = B[l];
}
}
void merge_sort(int A[], int B[], int left, int right) {
int mid;
if (left == right || left == right - 1) { return; }
mid = (left + right) / 2;
merge_sort(A, B, left, mid);
merge_sort(A, B, mid, right);
merge(A, B, left, mid, right);
}
int main(void) {
int a[10] = {8,4,7,2,1,3,5,6,9,10};
int b[10] = {0};
const int n = 10;
int i;
merge_sort(a, b, 0, n);
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
Rubydef mergesort lst
return _mergesort_ lst.dup # 副作用で配列が壊れるので、複製を渡す
end
def _mergesort_ lst
if (len = lst.size) <= 1 then
return lst
end
# pop メソッドの返す値と副作用の両方を利用して、lst を二分する
lst2 = lst.pop(len >> 1)
return _merge_(_mergesort_(lst), _mergesort_(lst2))
end
def _merge_ lst1, lst2
len1, len2 = lst1.size, lst2.size
result = Array.new(len1 + len2)
a, b = lst1[0], lst2[0]
i, j, k = 0, 0, 0
loop {
if a <= b then
result[i] = a
i += 1 ; j += 1
break unless j < len1
a = lst1[j]
else
result[i] = b
i += 1 ; k += 1
break unless k < len2
b = lst2[k]
end
}
while j < len1 do
result[i] = lst1[j]
i += 1 ; j += 1
end
while k < len2 do
result[i] = lst2[k]
i += 1 ; k += 1
end
return result
end
Haskell（※ Haskellのリストは「長さを測って半分ずつに分ける」という操作には適さないため、要素を1個ずつ振り分ける関数を使っている。この実装では安定ではない） mergesort :: Ord t => [t] -> [t]
mergesort lst = case lst of
[] -> lst
[_] -> lst
_ -> merge (mergesort a) (mergesort b)
where
(a, b) = split lst
merge [] [] = []
merge xxs [] = xxs
merge [] yys = yys
merge xxs@(x : xs) yys@(y : ys)
| x < y = x : (merge xs yys)
| otherwise = y : (merge xxs ys)
split [] = ([], [])
split ~(x : xs) = (x : zs, ys)
where
(ys, zs) = split xs
Scheme;; use-modules は 処理系 Guile 固有の機能である。
;; SRFI 機能を使うための仕組み処理系に依る。
(use-modules (srfi srfi-1 )) ; split-at
(use-modules (srfi srfi-11)) ; let-values
(define (merge left-half right-half)
(let loop ((ls left-half) (rs right-half) (result (list)))
(cond
((null? rs) (append (reverse result) ls))
((null? ls) (append (reverse result) rs))
(else
(let ((l (car ls)) (r (car rs)))
(if (<= l r)
(loop (cdr ls) rs (cons l result))
(loop ls (cdr rs) (cons r result))))))))
(define (merge-sort xs)
(cond
((null? xs ) xs)
((null? (cdr xs)) xs)
(else
(let-values
(((left-half right-half)
(split-at xs (quotient (length xs) 2))))
(merge
(merge-sort left-half)
(merge-sort right-half))))))
アルゴリズムの動作例初期データ: 8 4 3 7 6 5 2 1
脚注
関連項目外部リンク
|
||||||||||||||||||||||||||||||||||||||
