何気なく始めた【ソート】シリーズ、Bubble Sort、Heap Sort、Quick Sortと進めましたが、今回がアルゴリズム紹介の最後で「シェルソート（Shell Sort）」をやります。（今回も詳しく調べられる方の為にwikiの参照を載せます。）
”Shell”というのが最初「貝」を連想させましたが、全く関係なくて、アルゴリズムを開発した方の名前なんですね。アルゴリズムは「（一定の距離をおいた）飛び飛びの列を（距離を縮めながら）繰り返しソートして、配列を大まかに整列された状態に近づけていく」（↑のwiki記事参照）というものです。
ではコードを見てゆきます。
//////////////
// Shell Sort
//////////////
//シェルソートは配列要素を一定の距離を置いたグループに分けて比較、交換を行いソートする方法
void shellsort(int *v, int n) {
int gap, i, j, temp; //gapは比較、交換する要素間の距離
for(gap = n / 2; gap > 0; gap /= 2) { //初期的な距離は配列サイズの1/2とする
for(i = gap; i < n; i++) { //距離は徐々に狭まってゆく
for(j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
//v[j]とv[j + gap]を交換する（解説：if文が無いのはforの条件に反映しているから）
temp = v[j];
v[j] = v[j + gap];
v[j + gap] = temp;
}
}
}
今回も実際に処理の動きを見て行きましょう。
配列 = {2, 7, 3, 5, 8, 0, 6, 1, 4};
要素数 9
１．３つのforループ
解説：距離（gap）を要素数の半分(4)にし、第2のforループでgapから末尾迄進め、第3のforループでgap間の2要素を比較、交換する。
配列 = {2, 7, 3, 5, 8, 0, 6, 1, 4};
↑ ↑
比較対象 > gap → 交換
配列 = {2, 0, 3, 5, 8, 7, 6, 1, 4};
配列 = {2, 0, 3, 5, 8, 7, 6, 1, 4};
↑ ↑
比較対象 > gap → 交換
配列 = {2, 0, 3, 1, 8, 7, 6, 5, 4};
配列 = {2, 0, 3, 1, 8, 7, 6, 5, 4}; //第3のループ2回目
↑ ↑
比較対象 > gap → 交換なし
配列 = {2, 0, 3, 1, 4, 7, 6, 5, 8}; //第3のループ2回目
解説：第2ループのカウンターiがnになったので第2ループを抜ける。
２．再度３つのforループ
解説：第1のループで距離（gap）を半分(2)にし、同様に第2、第3のforループでgap間の2要素を比較、交換する。
配列 = {2, 0, 3, 1, 4, 7, 6, 5, 8};
↑ ↑
比較対象>gap → 交換
配列 = {2, 0, 3, 1, 4, 5, 6, 7, 8};
解説：第2ループのカウンターiがnになったので第2ループを抜ける。
３．再々度３つのforループ
解説：第1のループで距離（gap）を半分(1)にし、同様に第2、第3のforループでgap間の2要素を比較、交換する。
配列 = {2, 0, 3, 1, 4, 5, 6, 7, 8};
↑ ↑
｜ gap
比較対象 → 交換
配列 = {0, 2, 3, 1, 4, 5, 6, 7, 8};
配列 = {0, 2, 3, 1, 4, 5, 6, 7, 8};
↑ ↑
｜ gap
比較対象 → 交換
配列 = {0, 2, 1, 3, 4, 5, 6, 7, 8};
配列 = {0, 2, 1, 3, 4, 5, 6, 7, 8};
↑ ↑
｜ gap
比較対象 → 交換
配列 = {0, 1, 2, 3, 4, 5, 6, 7, 8};
如何でしたでしょうか？あっさりとソートされた、という感じですかね？
これで主たるソートアルゴリズムの紹介を終えますが、（ドラゴンボールみたいに）【ソート】シリーズはもうちょっと続きます。
【ご参考】（解説：↑の例のshellsortソート実行中の配列変化の出力）
>>> オリジナルデータ <<<
2, 7, 3, 5, 8, 0, 6, 1, 4
>>> Shell Sort started ... <<<
>>> 第0回目の交換 <<<
2, 0, 3, 5, 8, 7, 6, 1, 4
>>> 第1回目の交換 <<<
2, 0, 3, 1, 8, 7, 6, 5, 4
>>> 第2回目の交換 <<<
2, 0, 3, 1, 4, 7, 6, 5, 8
>>> 第3回目の交換 <<<
2, 0, 3, 1, 4, 5, 6, 7, 8
>>> 第4回目の交換 <<<
0, 2, 3, 1, 4, 5, 6, 7, 8
>>> 第5回目の交換 <<<
0, 2, 1, 3, 4, 5, 6, 7, 8
>>> 第6回目の交換 <<<
0, 1, 2, 3, 4, 5, 6, 7, 8
>>> Shell Sort completed! <<<
0, 1, 2, 3, 4, 5, 6, 7, 8
Push CR key ...