アルゴリズムとデータ構造 補足資料 8-2 「マージソート merge.c 」

アルゴリズムとデータ構造 補足資料 8-2

「マージソート merge.c 」

横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： ストリーム：先頭から順に読む。（現在地を読み出せる）

最後尾に書く。（末尾に書き足せる）

マージソート

65 90

85 70

86 92

63 85

入力列 A

入力列 B

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： ストリーム：先頭から順に読む。（現在地を読み出せる）

最後尾に書く。（末尾に書き足せる）

マージソート

65 90

85 70

86 92

63 85

入力列 A

入力列 B

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： ストリーム：先頭から順に読む。（現在地を読み出せる）

最後尾に書く。（末尾に書き足せる）

マージソート

65 90

85 70

86 92

63

85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65 90

85 70

86 92

63

85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90

85 70

86 92

63

85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90

85 70

86 92

63

85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90

85 70

86 92

63

85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90

85 70

86 92

63

85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90 85

70

86 92

63

85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90 85

70

86 92

63

85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90 85

70

86 92

63 85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90 85

70 86

92

63 85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65

90 85

70 86

92

63 85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65 70 85 86 90 92

63 85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65 70 85 86 90 92

63 85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

65 70 85 86 90 92

63 85

出力列

入力列 B

入力列 A

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

補足： 入力のストリーム： 先頭から順に読む。（現在地を読み出せる）

出力のストリーム： 最後尾に書く。（末尾に書き足せる）

マージソート

とりあえず、これでいいです。

が、

「ディスク」のように「順アクセス」は得意だが「ランダムアクセス」にはちと時間がかかる デバイスで、順アクセスだけを使ってソートするには。。。

→ サンプルプログラム

「マージ」の本質：

先頭から読んで（小さい方を） 、末尾にくっつける

8 件のデータ

65 90 85 70 86 92 63 85

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

8 件のデータ

65 90 85 70 86 92 63 85

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

65 90 85 70 86 92 63 85

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

1 個ずつのストリームとしてマージ！

65 90 85 70 86 92 63 85

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

1 個ずつのストリームとしてマージ！

65 86

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

90 85 70 92 63 85

1 個ずつのストリームとしてマージ！

90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

65 86

85 70 63 85

1 個ずつのストリームとしてマージ！

65 90

86 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85 70 63 85

1 個ずつのストリームとしてマージ！

65 90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

1 個ずつのストリームとしてマージ！

65 90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

1 個ずつのストリームとしてマージ！

65 90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

1 個ずつのストリームとしてマージ！

65 90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

1 個ずつのストリームとしてマージ！

65 90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

できたストリームを

次の入力ストリームとする

65 90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

2 個ずつのストリームとしてマージ！

65 90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

2 個ずつのストリームとしてマージ！

65 90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

2 個ずつのストリームとしてマージ！

65

90

85 86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

2 個ずつのストリームとしてマージ！

65

90

85

86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

2 個ずつのストリームとしてマージ！

65 90

85

86

92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

2 個ずつのストリームとしてマージ！

65 90

85

86 92

63

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

70 85

2 個ずつのストリームとしてマージ！

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

2 個ずつのストリームとしてマージ！

85 63

70 85

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

2 個ずつのストリームとしてマージ！

85

63

70 85

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

2 個ずつのストリームとしてマージ！

85

63 70

85

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

2 個ずつのストリームとしてマージ！

85 63 70

85

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

2 個ずつのストリームとしてマージ！

85

63 70 85

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85

63 70 85

できたストリームを

次の入力ストリームとする

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85

63 70 85

4 個ずつのストリームとしてマージ！

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85 63

70 85

4 個ずつのストリームとしてマージ！

65

90

86 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85 63

70 85

4 個ずつのストリームとしてマージ！

65

90

86 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85

63 70

85

4 個ずつのストリームとしてマージ！

65

90

86 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85

63 70

85

4 個ずつのストリームとしてマージ！

65

90

86 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85

63 70 85

4 個ずつのストリームとしてマージ！

65

90

86

92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85

63 70 85

4 個ずつのストリームとしてマージ！

65 86 90

92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85

63 70 85

4 個ずつのストリームとしてマージ！

65 86 90 92

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

85

63 70 85

4 個ずつのストリームとしてマージ！

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

解の方針：ソート済みの二つの列（ストリーム）を「合流」（マージ）させる。

（ランダムアクセスができない場合：順アクセスデータ、に向くアルゴリズム）

マージソート

n 件のデータ 未整列 未整列

未整列

整列済

log

n

O(n x log n)