Data-structures-algorithms-insertion-sort-algorithm
データ構造とアルゴリズムの挿入ソート
これは、インプレース比較ベースのソートアルゴリズムです。 ここでは、常にソートされるサブリストが維持されます。 たとえば、配列の下部はソートされるように維持されます。 このソートされたサブリストに「挿入」される要素は、適切な場所を見つけてから、そこに挿入する必要があります。 したがって、名前は*挿入ソート*です。
配列が順番に検索され、ソートされていない項目が移動され、ソートされたサブリスト（同じ配列内）に挿入されます。 このアルゴリズムは、その平均および最悪の場合の複雑さがΟ（n ^ 2 ^）であるため、大きなデータセットには適していません。
挿入ソートの仕組み
この例では、ソートされていない配列を使用します。
挿入ソートは、最初の2つの要素を比較します。
14と33の両方がすでに昇順であることがわかります。 今のところ、14はソートされたサブリストにあります。
挿入ソートは先に進み、33と27を比較します。
そして、33が正しい位置にないことがわかります。
33と27を入れ替えます。 また、ソートされたサブリストのすべての要素をチェックします。 ここで、ソートされたサブリストには要素が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 procedureCプログラミング言語での挿入ソートの実装については、リンク：/data_structures_algorithms/insertion_sort_program_in_c [ここをクリック]を参照してください。
