一回のスキャンは次のような操作になります。
配列の後ろから前に向かって要素を二つずつ比較して、 右の方が小さければ入れ替えます。 小さい要素が泡のように浮いてくるので、バブルソートと呼ばれています。
ここでは、初等的なソート方法 （アルゴリズムＣ 第１巻 p.107） について学びます。
(1) 次のように並んでいる数列を、バブルソート、挿入ソート、選択ソート を用いてソートしなさい。ただし、途中の過程も書くこと。
9 6 7 1 2
(2) 次のように並んでいる数列を、 シェルソートを用いてソートしなさい。ただし、途中の過程も書くこと。
5 1 4 3 8 2 6 7
(1) の三種類のソート方法は、最も遅いものに分類されます。 どの方法も計算量は O(n2) です。 以下の図を参考にして、並び換えてください。 縦棒より左側がソート済みであることを表わしています。
バブルソート（アルゴリズムＣ 第１巻 p.116）
一回のスキャンは次のような操作になります。
配列の後ろから前に向かって要素を二つずつ比較して、
右の方が小さければ入れ替えます。
小さい要素が泡のように浮いてくるので、バブルソートと呼ばれています。
挿入ソート（アルゴリズムＣ 第１巻 p.113）
縦棒の右隣の要素を左側の適当な場所に挿入していきます。
トランプを並べ替えるとき、大抵の人はこの方法を使っていると思います。
選択ソート（アルゴリズムＣ 第１巻 p.111）
縦棒より右側で一番小さいものを、縦棒の左隣と交換していきます。
(2) 挿入ソートを改良したものが、このシェルソート
（アルゴリズムＣ 第１巻 p.123）
です。
一定間隔で離れた要素だけで並べ替えを行なって、間隔を狭めていきます。
最後の 1-ソート が挿入ソートにあたります。
シェルソートよりも余計な手間（4-ソート と 2-ソート）がかかって、
むしろ遅くなりそうですが、かなり速いソート方法です。
バブルソート、挿入ソート、選択ソートでソートを行うプログラムを作成しなさい。 プログラムは以下の条件を満たすこと。（ex08-2-skel.c）
実行例： % ./a.out Before: 7 1 6 5 2 Select a method (1:buble, 2:insertion: 3: selection) > 1 1 7 2 6 5 1 2 7 5 6 1 2 5 7 6 1 2 5 6 7 % ./a.out Before: 7 1 6 5 2 Select a method (1:buble, 2:insertion: 3: selection) > 2 1 7 6 5 2 1 6 7 5 2 1 5 6 7 2 1 2 5 6 7 % ./a.out Before: 7 1 6 5 2 Select a method (1:buble, 2:insertion: 3: selection) > 3 1 7 6 5 2 1 2 6 5 7 1 2 5 6 7 1 2 5 6 7
ソートの途中でデータにない変な数字が出てきた場合は、 ループの範囲が間違っている可能性が高いので、 そこをもう一度見直してください。
シェルソートを行う関数を作り、 問題２で作った挿入ソートと速度を比較しなさい。 プログラムは以下の条件を満たすこと。（ex08-3-skel.c）
実行例（シェルソートの具体的な数値は伏せてあります）： % ./a.out insertion sort: elapsed time 316.239708. shell sort: elapsed time ********.
同じ条件で比較するために、使用するデータは同じものを用意してください。 まず、配列 a に 100000 個の乱数を入れて、 そのあと配列 b に配列 a の内容をコピーし、 挿入ソートで配列 a をソートし、 シェルソートで配列 b をソートするとやりやすいでしょう。
まずはデータの個数を 10 個くらいにし、配列 a, b の内容を ソート前とソート後に表示して、うまく動いているかを確認してください。 データの個数が少ないうちは、実は挿入ソートの方が速いはずです。 興味のある人は、データの個数がいくつくらいになるとシェルソートの方が 速くなるか試してみてください。