データ構造とアルゴリズム挿入ソート
これは、インプレース比較ベースのソートアルゴリズムです。ここでは、常にソートされるサブリストが維持されます。たとえば、配列の下部はソートされるように維持されます。このソートされたサブリストに「挿入」される要素は、適切な場所を見つけてから、そこに挿入する必要があります。したがって、名前は、insertion sort。
配列は順番に検索され、並べ替えられていないアイテムが移動され、並べ替えられたサブリスト(同じ配列内)に挿入されます。このアルゴリズムは、平均および最悪の場合の複雑さがΟ(n 2)であるため、大規模なデータセットには適していません。n アイテムの数です。
挿入ソートはどのように機能しますか?
例として、ソートされていない配列を取り上げます。
挿入ソートは最初の2つの要素を比較します。
14と33の両方がすでに昇順であることがわかります。今のところ、14はソートされたサブリストにあります。
挿入ソートは先に進み、33と27を比較します。
そして、33が正しい位置にないことがわかります。
33を27に交換します。また、ソートされたサブリストのすべての要素をチェックします。ここでは、ソートされたサブリストには要素14が1つしかなく、27は14より大きいことがわかります。したがって、ソートされたサブリストは、スワップ後もソートされたままになります。
これで、ソートされたサブリストに14と27が含まれます。次に、33と10を比較します。
これらの値はソートされた順序ではありません。
だから私たちはそれらを交換します。
ただし、スワッピングすると27と10がソートされなくなります。
したがって、それらも交換します。
ここでも、14と10がソートされていない順序で見つかります。
再度交換します。3回目の反復の終わりまでに、4つのアイテムのソートされたサブリストができました。
このプロセスは、ソートされていないすべての値がソートされたサブリストでカバーされるまで続きます。ここで、挿入ソートのプログラミングの側面をいくつか見ていきます。
アルゴリズム
これで、このソート手法がどのように機能するかについての全体像がわかったので、挿入ソートを実現するための簡単な手順を導き出すことができます。
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
擬似コード
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure
Cプログラミング言語での挿入ソートの実装については、ここをクリックしてください。