エクセルVBAで挿入ソート - 午後わてんのブログ

挿入ソート、InsertionSort

挿入ソート - Wikipedia
https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88

今までのバブルソートからコムソートは交換して並べ替えていた

挿入ソートは名前の通り挿入して並べ替えていく

3,5,6って整列されているところに4が来たら3と5の間に4を挿入

挿入される側は整列されている必要があるので、配列でいったら左側から順番に比較挿入していけばいいことになる

5,3,6,4のときは

左から見ていくと5のところに3が来たので5の前に3を挿入

次は3,5のところに6なので5の後ろに挿入

次は3,5,6のところに4は3と5の間に挿入

まとめると

交換していくバブルソートよりこっちのほうが直感的かなあ、本棚の本を整列するときはこんな感じ

WikipediaにあるC言語で書かれたコードを真似しようとしてみたけど、うまくできなくて↓こうなった

Function testInsertion2(v As Variant) As Variant
    Dim i As Long, j As Long
    Dim tmp As Variant
    For i = LBound(v) + 1 To UBound(v)
        tmp = v(i)
        For j = i - 1 To LBound(v) Step -1
            If v(j) > tmp Then
                v(j + 1) = v(j)
            Else
                Exit For
            End If
        Next
        v(j + 1) = tmp
    Next
    testInsertion2 = v
End Function

適当な変数tmpに挿入する数値を入れておいて、	tmp = v(i)
これを右から左の数値と比較していって、		If v(j) > tmp Then
比較数値>tmpなら比較数値を右へコピー、		v(j + 1) = v(j)
比較数値>tmpじゃなければ内側のループを抜ける、	Exit For
最後にtmpを挿入して、					v(j + 1) = tmp
次の外側ループへ

コードにするとバブルソートとあんまり変わらないんだよねえ、とくにtestBubble3とはかなり似ている