挿入ソート
挿入ソートはバブルソートを一歩進めたもので、基本的には同じ原理で動作します。ループを使ってリストの最初から最後まで調査するところは変わりませんが、要素を入れ替えていくのではなく、既にソートされている部分に対して、その中の正しい位置に要素を挿入します。
リストを降順でソートする場合、バブルソートと挿入ソートではソートにかかる時間は同程度となるでしょう。しかし、リストがある程度ソートされている場合は、挿入ソートの方が早く完了します。
挿入ソートで興味深いのは、n回の処理が終わった時点でリストの最初のn個がソートされた状態になりますが、それらの要素が最終的に正しい位置にあるとは限らないという点です。
挿入ソートが他のソートアルゴリズムに比べて優れているのは、たとえばユーザーが入力しているリスト項目や、外部デバイスからの入力データなど、要素をリアルタイムでソートする際に利用できることです。この目的に関しては、他のほとんどのソート方式よりもかなり高速です。
挿入リストのコード例をコードリスト4に示します。
For Loop1 = 1 To Total Tmp = List(Loop1) For Loop2 = Loop1 To 1 Step -1 If List(Loop2 - 1) > Tmp Then List(Loop2) = List(Loop2 - 1) Else Exit For End If Next Loop2 List(Loop2) = Tmp Next Loop1
選択ソート
選択ソートは挿入ソートとバブルソートの中間にあたり、リストの未ソート部分の中から最小値を見つけ出して先頭に配置します。選択ソートでは、要素を前方や後方に1つずつ移動するのではなく、要素の位置を交換することで正しい配置にするので、この手法を交換ソートと呼ぶこともよくあります。
選択ソートで特筆すべき長所はあまりないのですが、配列への書き込みを行う際に比較的長いメモリアクセス時間がかかる記憶装置（たとえばEEPROMやFlashメモリなど）では、要素の交換回数が少ない選択ソートの方が、他のほとんどのソート方式よりも高速に実行できます。
選択ソートの特徴は、n回の処理が完了した時点で要素の交換がn回だけ実行され、最初のn個の要素がソート済みの正しい位置に配置されるという点です。
選択ソートの例をコードリスト5に示します。
For Loop1 = 0 To Total Pos = Loop1 For Loop2 = Loop1 + 1 To Total If List(Loop2) < List(Pos) Then Pos = Loop2 End if Next Loop2 If Pos <> Loop1 Then Tmp = List(Pos) List(Pos) = List(Loop1) List(Loop1) = Tmp End If Next Loop1
ヒープソート
ヒープソートでは二段階のソートを行います。まず予備ソートを行ってリスト内に親子ツリーを作成し、次にその親子ツリーを使ってリスト全体をソートします。
ヒープソートを実装するにはいくつか方法があり、そのうちのいくつかのアルゴリズムでは別の配列を用意してソートを実行します。今回紹介するコードリストは、元々のリストの内部でヒープソートを行う方法を採用しており、最適化も行われています。
始めの段階では、リストは最初の時点よりもバラバラな順序になったように見えます。しかし実際には、リスト内の最大の要素が頂点にあるような形式のソート用の親子ツリーが作成されています。次の段階では、n回の処理が完了した時点で、最後のn個の要素がソートされて正しい位置に配置されます。親子ツリーでは、処理のたびに次の最大要素を頂点に移動させるようにします。
ヒープソートには1つ弱点があります。コードサイズが大きくなるため、コードに利用できるメモリの大きさが限られているプロジェクト（マイクロコントローラーやプログラム可能なPICなど）で使用するのは実用的でないという点です。
コードサイズの問題はありますが、メモリの読み取り時間と書き出し時間にあまり差がないシステムでは、ヒープソートは最も高速な非再帰のソート手法として長年利用されてきました。
コードリスト6に、実行可能なヒープソートの例を示します。
For Loop1 = 1 To Total PercolateUp Loop1 Next Loop1 For Loop1 = Total To 1 Step -1 Swap 0, Loop1 PercolateDown Loop1 - 1 Next Loop1 Sub PercolateUp(MaxLevel) Loop2 = MaxLevel Do Until Loop2 = 0 Parent = Loop2 \ 2 If List(Loop2) > List(Parent) Then Tmp = List(Loop2) List(Loop2) = List(Loop2 + 1) List(Loop2 + 1) = Tmp Loop2 = Parent Else Exit Do End If Loop Sub PercolateDown(MaxLevel) Loop2 = 0 Do Child = 2 * Loop_2 If Child > MaxLevel Then Exit Do If Child + 1 <= MaxLevel Then If List(Child + 1) > List(Child) Then Child = Child + 1 End If End If If List(Loop_2) < List(Child) Then Tmp = List(Loop2) List(Loop2) = List(Loop2 + 1) List(Loop2 + 1) = Tmp Loop_2 = Child Else Exit Do End If Loop
