並び替えの基本ロジックの２回目です。
今回は、シェル・ソートの基本的部分「単純挿入法」を取り上げてみます。

この練習では、Excel のセルを数字の入力域および出力域として利用します。
Sheet1 のセルA1〜A5 に、適当な整数を入れておいてください。

この「単純挿入法」のロジックは簡単に言うと、２番目の数字から自分より前の数字と大小比較を始めて、自分の置かれるべき場所（常に自分より前）に移動していくものです。
例えば、３番目の数字が一番小さいとしますと、３番目の数字は１番目に移動し、１〜２番目の数字は１つずつ後ろに移動します。 これは３番目の数字が一番前に挿入された形ですので、「挿入法」という名前が付いたのだと思われます。

では、例を出してみましょう。

例：５０，３０，２０，４０，１０ の５つの数字を、小さい順に並べ替えます。

1. ２番目の数字３０から始めます。
   自分の前の数字と比較して、自分の置かれるべき位置を見つけます。
   
   
2. 自分（今は２番目の数字３０）の前の数字は、１番目の数字５０です。
   　↓──↓
   ５０，３０，２０，４０，１０
   
   自分（３０）は５０より小さいので１番目に入り、５０は１つ後ろにずれます。
   すると、３０，５０，２０，４０，１０となります。
   もし１番目の数字が自分より小さかったら、何もしません。
   
   
   
3. 次は３番目で、前の数字と比較して、自分の置かれるべき位置を見つけます。
   
   
   
4. まず自分（３番目の数字２０）の前の数字の、１番目の数字３０と比較します。
   　↓─────↓
   ３０，５０，２０，４０，１０
   
   自分（２０）は３０より小さいので１番目に入り、３０と５０は１つずつ後ろにずれます。
   すると、２０，３０，５０，４０，１０となります。
   
   もし１番目の数字が自分より小さかったら、２番目の数字と比較します。
   もし１番目の数字も２番目の数字も、自分より小さかったら、何もしません。
   
   
   
5. 次は４番目で、前の数字と比較して、自分の置かれるべき位置を見つけます。
   
   
   
6. まず自分（４番目の数字４０）の前の数字の、１番目の数字２０と比較します。
   　↓────────↓
   ２０，３０，５０，４０，１０
   自分（４０）は２０より大きいので、何もしません。 もし自分が１番目の数字より小さかったら、自分が１番目に挿入されることは、わかりますね。
   
   
7. 自分（４番目の数字４０）の前の数字の、２番目の数字３０と比較します。
   　　　　↓─────↓
   ２０，３０，５０，４０，１０
   自分（４０）は３０より大きいので、何もしません。 もし自分が２番目の数字より小さかったら、自分が２番目に挿入されることは、書かなくてもよいですよね。
   
   
8. 自分（４番目の数字４０）の前の数字の、３番目の数字５０と比較します。
   　　　　　　　↓──↓
   ２０，３０，５０，４０，１０
   
   自分（４０）は５０より小さいので３番目に入り、５０は１つずつ後ろにずれます。
   すると、２０，３０，４０，５０，１０となります。
   
   
   
9. さて、最後の５番目で、前の数字と比較して、自分の置かれるべき位置を見つけます。
   
   
   
10. 自分（５番目の数字１０）の前の数字の、１番目の数字２０と比較します。
    　↓───────────↓
    ２０，３０，４０，５０，１０
    
    自分（１０）は２０より小さいので１番目に入り、１〜４番目の数字は１つずつ後ろにずれます。 大移動ですね。
    すると、１０，２０，３０，４０，５０となります。
    
    これで、小さい順に並び終わりましたが、プログラム上は「１番目の数字が自分より大きい場合」や、 「２〜４番目の数字が自分より小さい場合」などを考慮に入れるべきなのは言うまでもありません。
    
    

このロジックは、前回の「選択法」や、初級２の練習４の「交換法」と比べて、難しいでしょうか？ 今のところ、どれが一番易しそうですか？

さて、ロジックは理解できたとしまして、いよいよこれをプログラムにするわけですが、 どんなプログラムになるか、わかりますか？

プログラム的には、一番難しいかもしれません。 何故なら、３重のループになるからです。
でもまず、ループを意識しないで、ループなしで考えてみましょう。 （実は、ループなしだと、とても大変なのですが・・・）

1. 小さいほうの数字を入れる変数を宣言します。
   Dim Smaller　　As Long '小さいほうの数字
   
   
   
2. ２番目の数字から始めます。
   自分（今は２番目の数字）の前の数字は、１番目の数字です。
   １番目の数字と大小比較します。
   If Cells(1, 2) < Cells(1, 1) Then　　'２番目の数字が１番目の数字未満なら
   　　自分は１番目に入り、もとの１番目の数字は１つ後ろにずれます。
   　　Smaller = Cells(1, 2)　　　　　　'小さいほうの数字 ← ２番目の数字
   　　Cells(1, 2) = Cells(1, 1)　　　　'２番目 ← １番目の数字
   　　Cells(1, 1) = Smaller　　　　　　'１番目 ← 小さいほうの数字
   End If　　　　　　'自分のほうが大きい場合は、何もしない
   
   
   
3. 次は、３番目の数字です。
   自分（３番目の数字）と１番目の数字とを、大小比較します。
   If Cells(1, 3) < Cells(1, 1) Then　　'３番目の数字が１番目の数字未満なら
   　　自分は１番目に入り、もとの１〜２番目の数字は１つずつ後ろにずれます。
   　　Smaller = Cells(1, 3)　　　　　　'小さいほうの数字 ← ３番目の数字
   　　Cells(1, 3) = Cells(1, 2)　　　　'３番目 ← ２番目の数字
   　　Cells(1, 2) = Cells(1, 1)　　　　'２番目 ← １番目の数字
   　　Cells(1, 1) = Smaller　　　　　　'１番目 ← 小さいほうの数字
   Else　　　　　　'自分のほうが大きい場合は、次へ
   
   
   
4. ３番目の数字が１番目の数字より大きい場合、２番目の数字と大小比較します。
   　　If Cells(1, 3) < Cells(1, 2) Then　　'３番目の数字が２番目の数字未満なら
   　　　　自分は２番目に入り、もとの２番目の数字は１つ後ろにずれます。
   　　　　Smaller = Cells(1, 3)　　　　　　'小さいほうの数字 ← ３番目の数字
   　　　　Cells(1, 3) = Cells(1, 2)　　　　'３番目 ← ２番目の数字
   　　　　Cells(1, 2) = Smaller　　　　　　'２番目 ← 小さいほうの数字
   　　End If　　　　　　'自分のほうが大きい場合は、何もしない
   End If　　　　　　'If と End If の数を合わせること
   
   
   
5. ４番目の数字の番です。
   自分（４番目の数字）と１番目の数字とを、大小比較します。
   If Cells(1, 4) < Cells(1, 1) Then　　'４番目の数字が１番目の数字未満なら
   　　自分は１番目に入り、もとの１〜３番目の数字は１つずつ後ろにずれます。
   　　Smaller = Cells(1, 4)　　　　　　'小さいほうの数字 ← ４番目の数字
   　　Cells(1, 4) = Cells(1, 3)　　　　'４番目 ← ３番目の数字
   　　Cells(1, 3) = Cells(1, 2)　　　　'３番目 ← ２番目の数字
   　　Cells(1, 2) = Cells(1, 1)　　　　'２番目 ← １番目の数字
   　　Cells(1, 1) = Smaller　　　　　　'１番目 ← 小さいほうの数字
   Else　　　　　　'自分のほうが大きい場合は、次へ
   
   
   
6. ４番目の数字が１番目の数字より大きい場合、２番目の数字と大小比較します。
   　　If Cells(1, 4) < Cells(1, 2) Then　　'４番目の数字が２番目の数字未満なら
   　　　　自分は２番目に入り、もとの２〜３番目の数字は１つずつ後ろにずれます。
   　　　　Smaller = Cells(1, 4)　　　　　　'小さいほうの数字 ← ４番目の数字
   　　　　Cells(1, 4) = Cells(1, 3)　　　　'４番目 ← ３番目の数字
   　　　　Cells(1, 3) = Cells(1, 2)　　　　'３番目 ← ２番目の数字
   　　　　Cells(1, 2) = Smaller　　　　　　'２番目 ← 小さいほうの数字
   　　Else　　　　　　'自分のほうが大きい場合は、次へ
   
7. ４番目の数字が２番目の数字より大きい場合、３番目の数字と大小比較します。
   　　　　If Cells(1, 4) < Cells(1, 3) Then　　'４番目の数字が３番目の数字未満なら
   　　　　自分は３番目に入り、もとの３番目の数字は１つ後ろにずれます。
   　　　　　　Smaller = Cells(1, 4)　　　　　　'小さいほうの数字 ← ４番目の数字
   　　　　　　Cells(1, 4) = Cells(1, 3)　　　　'４番目 ← ３番目の数字
   　　　　　　Cells(1, 3) = Smaller　　　　　　'３番目 ← 小さいほうの数字
   　　　　End If　　　　　　'自分のほうが大きい場合は、何もしない
   　　End If　　　　　　'If と End If の数を合わせること
   End If　　　　　　'If と End If の数を合わせること
   
   
   

説明は、ここまでにします。 ５番目の数字の場合どうするかは、各自で考えて完成させてください。
さらには Do 〜 Loop を使って、５つの数字でなく、もっとたくさんの数字の並び替えができるようにしてください。

３重のループになると書きましたが、まずは１重のループから考えてみてください。

ヒントは・・・ここ↓
　　Smaller = Cells(1, 4)　　　　　　'小さいほうの数字 ← ４番目の数字
　　Cells(1, 4) = Cells(1, 3)　　　　'４番目 ← ３番目の数字
　　Cells(1, 3) = Cells(1, 2)　　　　'３番目 ← ２番目の数字
　　Cells(1, 2) = Cells(1, 1)　　　　'２番目 ← １番目の数字
　　Cells(1, 1) = Smaller　　　　　　'１番目 ← 小さいほうの数字
１つずつ ずらすところですね。

もう１つヒントを。
今までは、ループカウンター(i など)を 1 ずつ足していきましたが、今回は 1 ずつ引いていってください。

それでは、また次回まで！