マージソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:16 UTC 版)
ナビゲーションに移動 検索に移動 
マージソートの例。まずリストを小さな単位に分け、二つのリストをそれぞれの要素の先頭を比較してマージする。最後までこの操作をくり返すと、リストはソートされている。
|
|
| クラス | ソート |
|---|---|
| データ構造 | 配列 |
| 最悪計算時間 | 
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を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
脚注
関連項目外部リンク |
マージソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/19 03:24 UTC 版)
「Standard ML」の記事における「マージソート」の解説
マージソートのアルゴリズムについては、当該記事を参照されたい。ここではマージソートを3つの関数 split、merge、MergeSort で実装している。 関数 split は、追加の引数を持つ局所関数 split_iter を使って実装している。これは末尾再帰の実装に便利な手法である。この関数はSMLのパターンマッチング構文を使っており、リストが空でないケース ('x::xs') と空のケース ('[]') を定義している。 (* 要素のリストを与えられ、それをほぼ同じサイズの * 2つに分割する。 * O(n) *) local fun split_iter (x::xs, left, right) = split_iter(xs, right, x::left) | split_iter ([], left, right) = (left, right) in fun split(x) = split_iter(x,[],[]) end; local-in-end という構文を let-in-end という構文に置き換えると、等価な定義が得られる。 fun split(x) = let fun split_iter (x::xs, left, right) = split_iter(xs, right, x::left) | split_iter ([], left, right) = (left, right) in split_iter(x,[],[]) end; split と同様、merge も局所関数 merge_iter を使って効率化する。merge_iter ではいくつかのケース（渡されたリストがどちらも空でない場合、一方が空の場合、両方が空の場合）を定義している。'_' はワイルドカード・パターンを表している。 この関数は2つの昇順のリストを1つの降順のリストにマージする。逆転するのはSMLにおけるリストの構造によるものである。SMLではリストを非平衡2分木で実装しているため、要素を先頭に付与するのは容易だが、最後尾に付与するのは非効率的である。 (* 2つの昇順リストを1つの降順リストにマージする。 * 関数 lt(a,b) は a < b と同値 * O(n) *) local fun merge_iter (out, left as (x::xs), right as (y::ys), lt) = if lt(x, y) then merge_iter(x::out, xs, right, lt) else merge_iter(y::out, left, ys, lt) | merge_iter (out, x::xs, [], lt) = merge_iter( x::out, xs, [], lt) | merge_iter (out, [], y::ys, lt) = merge_iter( y::out, [], ys, lt) | merge_iter (out, [], [], _) = out in fun merge(x,y,lt) = merge_iter([],x,y,lt) end; 最後に、MergeSort 関数を以下に示す。 (* リストを降順にソートする。順序は lt(a,b) <==> a < b で決定。 * O(n log n) *) fun MergeSort(empty as [], _) = empty | MergeSort(single as _::[], _) = single | MergeSort(x, lt) = let val (left, right) = split(x) val sl = MergeSort(left, lt) val sr = MergeSort(right, lt) val s = merge(sl,sr,lt) in rev s end; なお、見ての通りこのコードでは要素の型を規定していない。そのため、順序関数 lt さえあれば、どんな型の要素でもソートできる。型推論により、コンパイラは lt 関数のような複雑な型も含め、あらゆる変数の型を推論できる。
※この「マージソート」の解説は、「Standard ML」の解説の一部です。
「マージソート」を含む「Standard ML」の記事については、「Standard ML」の概要を参照ください。
マージソートと同じ種類の言葉
- マージソートのページへのリンク
