ピヨピヨ日記 シンガポール編

シンガポール生活の日記とかいろいろ

アルゴリズムのお勉強 - バブルソート2

下記の本を参考書として、アルゴリズムのお勉強をしてみる!2回目。  

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

 

 

前回のお勉強で作ったバブルソートのプログラムをより効率よく改良してみる。

 

前回のお勉強: アルゴリズムのお勉強 - バブルソート - ピヨピヨ日記 シンガポール編

 

参考書によると、バブルソートには、つぎのような性質があるとのことです。

「ループが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 が最大の数値であるということがわかっているので、最後の比較をスキップすることができます。

 

  • [324153と2を比較。3は2より大きいので入れ替える。[23415]
  • [23415] 3と4を比較。3は4より小さいのでそのまま。[23415]
  • [23415] 4と1を比較。4は1より大きいので入れ替える。[23145]
  • [231454と5を比較。4は5より小さいのでそのまま[23145] (スキップできる!)

 

つまり、前回のお勉強で作成していたバブルソートでは、配列の要素数 - 1ループごとに必要な比較の回数だったのですが、1回ループするごとに最後の要素の比較がスキップできるので、配列の要素数 - 1 - ループが終了した回数 が各ループごとに必要な比較の回数になります。

 

ということで Ruby で書いてみたプログラムがこちら

 

bubble_sort02.rb

 

[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

前回のプログラムとデータの交換回数は変わらないけど、比較回数が半分になった!おもしろい!