ソートとは、何らかの決まった順番に並べること。
ソートは奥が深い。
安定ソート
安定したソートとは、前回の並び順を保存しつつソートすること。
例えば名前と値の表がある場合、名前順にソートし、次に値順にソートすると
値が同じ項目では名前順になる。前回の並び順を保存しているからだ。
バブルソート
泡がポコポコ浮き上がるようにソートされる。
↓バブルソートの例
2,5,7,9,0,8,6,4,3,1 [0]スタート
2,5,7,0,8,6,4,3,1,9 [1]
2,5,7,0,6,4,3,1,8,9 [2]
2,5,0,6,4,3,1,7,8,9 [3]
2,5,0,4,3,1,6,7,8,9 [4]
2,0,4,3,1,5,6,7,8,9 [5]
0,2,3,1,4,5,6,7,8,9 [6]
0,2,1,3,4,5,6,7,8,9 [7]
0,1,2,3,4,5,6,7,8,9 [8]
0,1,2,3,4,5,6,7,8,9 [9]エンド
↓[0]から[1]の中では次のような動きになる。
[2,5],7,9,0,8,6,4,3,1 比較
2,[5,7],9,0,8,6,4,3,1 比較
2,5,[7,9],0,8,6,4,3,1 比較
2,5,7,[9,0],8,6,4,3,1 比較
2,5,7,[0,9],8,6,4,3,1 swap
2,5,7,0,[9,8],6,4,3,1 比較
2,5,7,0,[8,9],6,4,3,1 swap
2,5,7,0,8,[9,6],4,3,1 比較
2,5,7,0,8,[6,9],4,3,1 swap
2,5,7,0,8,6,[9,4],3,1 比較
2,5,7,0,8,6,[4,9],3,1 swap
2,5,7,0,8,6,4,[9,3],1 比較
2,5,7,0,8,6,4,[3,9],1 swap
2,5,7,0,8,6,4,3,[9,1] 比較
2,5,7,0,8,6,4,3,[1,9] swap
バブルソートの利点
バブルソートは一般的に無駄が多く”遅い”ソートだと言われている。
だが安定ソートであり、アルゴリズムが並列処理に向いている。
僕は個人的に、バブルソートが好きだ。
何故なら、プログラミングを始める人にお勧めできる問題になるからだ。
また安定したソートで、ループにデバッグプリントを入れると、
上記の例のように非常にきれいにソートされて行く様子が分かる。
その感動を、プログラミングを始める人にぜひ味わってほしいなあ。