挿入ソートは、私たちが手の中のトランプを並べ替えるのと同じように機能するシンプルな並べ替えアルゴリズムです。
挿入ソート用のPythonプログラム
insertSort 関数は、配列 arr を入力として受け取ります。まず、配列の長さ (n) を計算します。長さが 0 または 1 の場合、要素が 0 または 1 個の配列はすでにソートされているとみなされ、関数はすぐに戻ります。
複数の要素を持つ配列の場合、関数は 2 番目の要素から配列を反復処理します。現在の要素 (キーと呼ばれる) を取得し、それより前の配列の並べ替えられた部分の要素と比較します。キーがソートされた部分の要素よりも小さい場合、関数はその要素を右にシフトし、キー用のスペースを作成します。このプロセスは、キーの正しい位置が見つかるまで続き、キーはその位置に挿入されます。
提供された例は、挿入ソート アルゴリズムを使用したソート プロセスを示しています。初期配列 [12, 11, 13, 5, 6] は、insertSort 関数の対象となります。ソート後の配列は [5, 6, 11, 12, 13] になるはずです。このコードは、ソートされた配列を最終出力として出力します。
javatable
パイソン
セレンのチュートリアル
def> insertionSort(arr):> >n>=> len>(arr)># Get the length of the array> > >if> n <>=> 1>:> >return> # If the array has 0 or 1 element, it is already sorted, so return> >for> i>in> range>(>1>, n):># Iterate over the array starting from the second element> >key>=> arr[i]># Store the current element as the key to be inserted in the right position> >j>=> i>->1> >while> j>>>=> 0> and> key # Move elements greater than key one position ahead arr[j+1] = arr[j] # Shift elements to the right j -= 1 arr[j+1] = key # Insert the key in the correct position # Sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)> |
>
>
出力：
Sorted array is: [5, 6, 11, 12, 13]>
時間計算量: O(N2)
補助スペース: O(1)
完全な記事を参照してください 挿入ソート 詳細については！