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

下記の本を参考書として、アルゴリズムのお勉強をしてみる！ 

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

アルゴリズムの基本として、 まずはソートのお勉強。

その中でも、「バブルソート」から始めてみる。

バブルソートのアルゴリズムは下記の通り

1. 先頭から順番にデータをみていく。このとき、左右の並び順がおかしければ、左右を入れ替える。
2. データの最後までたどり着いたら、最初から同じようにデータをみていく。
3. 1度も並べ替えが行われずに、データを先頭から最後まで見終わったらソート完了。

例: 35241 を小さい順に並べ替える

• [35241] まず、3と5を比較。3は5より小さいのでデータはそのまま。[35241]
• [35241] つぎに、5と2を比較。5は2より大きいので入れ替える。[32541]
• [32541] 5と4を比較。5は4より大きいので入れ替える。[32451]
• [32451] 5と1を比較。5は1より大きいので入れ替える。[32415]
• 入れ替えがあったので、先頭に戻る。
• [32415] 3と2を比較。3は2より大きいので入れ替える。[23415]
• [23415] 3と4を比較。3は4より小さいのでそのまま。[23415]
• [23415] 4と1を比較。4は1より大きいので入れ替える。[23145]
• [23145] 4と5を比較。4は5より小さいのでそのまま。[23145]
• 入れ替えがあったので、先頭に戻る。
• [23145] 2と3を比較。2は3より小さいのでそのまま。[23145]
• [23145] 3と1を比較。3は1より大きいので入れ替える。[21345]
• [21345] 3と4を比較。3は4より小さいのでそのまま。[21345]
• [21345] 4と5を比較。4は5より小さいのでそのまま。[21345]
• 入れ替えがあったので、先頭に戻る
• [21345] 2と1を比較。2は1より大きいので入れ替える。[12345]
• [12345] 2と3を比較。2は3より小さいのでそのまま。[12345]
• [12345] 3と4を比較。3は4より小さいのでそのまま。[12345]
• [12345] 4と5を比較。4は5より小さいのでそのまま。[12345]
• 入れ替えがあったので、先頭に戻る。
• [12345] 1と2を比較。1は2より小さいのでそのまま。[12345]
• [12345] 2と3を比較。2は3より小さいのでそのまま。[12345]
• [12345] 3と4を比較。3は4より小さいのでそのまま。[12345]
• [12345] 4と5を比較。4は5より小さいのでそのまま。[12345]
• 入れ替えがなかったので、ソート完了！

Ruby で書いてみたプログラムはこちら

bubble_sort.rb

[3,5,2,4,1] という配列でまわしてみた結果はこちら

ソート開始: 2015-10-31 19:49:48 +0800
ソート前: [3, 5, 2, 4, 1]
ソート終了: 2015-10-31 19:49:48 +0800
ソート後: [1, 2, 3, 4, 5]
比較回数: 20
交換回数: 7

いちおう勉強用のリポジトリも作ってみた。

hm0429/Study_Algorithm · GitHub