データ構造とアルゴリズム挿入ソート

これは、インプレース比較ベースのソートアルゴリズムです。ここでは、常にソートされるサブリストが維持されます。たとえば、配列の下部はソートされるように維持されます。このソートされたサブリストに「挿入」される要素は、適切な場所を見つけてから、そこに挿入する必要があります。したがって、名前は、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プログラミング言語での挿入ソートの実装については、ここをクリックしてください。