下記の本を参考書として、アルゴリズムのお勉強をしてみる!2回目。
- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/30
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (31件) を見る
前回のお勉強で作ったバブルソートのプログラムをより効率よく改良してみる。
前回のお勉強: アルゴリズムのお勉強 - バブルソート - ピヨピヨ日記 シンガポール編
参考書によると、バブルソートには、つぎのような性質があるとのことです。
「ループが1回終了するごとに、配列の後方要素は確実にソート済みになっている」
出展: 紀平 拓男. 春日 伸弥,『プログラミングの宝箱 アルゴリズムとデータ構造 第2版』(ソフトバンククリエイティブ, 2011)
最初読んだときに何言っているのかよくわからなかったのですが、簡単にいうと、「数値の配列を小さい順に並べるといった例では、一番大きな数字が必ず一番後方に来るといった性質がある」ということです。前から順番にソートしていくのだからあたりまえといえばあたりまえですね。
もっと具体的にいうと、「35241」を小さい順に並べ替える、という例だと、1回目のループは下記のようになり、最大の数値である 5 が必ず一番後方に来ます。
- [35241] まず、3と5を比較。3は5より小さいのでデータはそのまま。[35241]
- [35241] つぎに、5と2を比較。5は2より大きいので入れ替える。[32541]
- [32541] 5と4を比較。5は4より大きいので入れ替える。[32451]
- [32451] 5と1を比較。5は1より大きいので入れ替える。[32415]
2回目のループでは、すでに一番後方の 5 が最大の数値であるということがわかっているので、最後の比較をスキップすることができます。
- [32415] 3と2を比較。3は2より大きいので入れ替える。[23415]
- [23415] 3と4を比較。3は4より小さいのでそのまま。[23415]
- [23415] 4と1を比較。4は1より大きいので入れ替える。[23145]
- [23145] 4と5を比較。4は5より小さいのでそのまま。[23145] (スキップできる!)
つまり、前回のお勉強で作成していたバブルソートでは、配列の要素数 - 1 が各ループごとに必要な比較の回数だったのですが、1回ループするごとに最後の要素の比較がスキップできるので、配列の要素数 - 1 - ループが終了した回数 が各ループごとに必要な比較の回数になります。
ということで Ruby で書いてみたプログラムがこちら
[3,5,2,4,1] という配列でまわしてみた結果はこちら
ソート開始: 2015-10-31 19:53:00 +0800
ソート前: [3, 5, 2, 4, 1]
ソート終了: 2015-10-31 19:53:00 +0800
ソート後: [1, 2, 3, 4, 5]
比較回数: 10
交換回数: 7
前回のプログラムとデータの交換回数は変わらないけど、比較回数が半分になった!おもしろい!