Pythonプログラムでの挿入ソート

この記事では、Python3.xでの挿入ソートの実装について学習します。またはそれ以前。

アルゴリズム

• ソートされた配列を各反復で拡張することにより、入力要素を反復します。

• 現在の要素を、並べ替えられた配列で使用可能な最大値と比較します。

• 現在の要素の方が大きい場合は、その要素をそのままにして次の要素に移動します。それ以外の場合は、並べ替えられた配列内で正しい位置を見つけて、配列内のその位置に移動します。

• これは、並べ替えられた配列内の現在の要素よりも大きいすべての要素を右にシフトすることで実現されます。

それでは、アルゴリズムの視覚的表現を見てみましょう

それでは、実装を見てみましょう

例

def insertionSort(arr):
   for i in range(1, len(arr)):
      key = arr[i]
      # Move elements of arr[0..i-1], that are greater
      than key,
      # to one position ahead of their current position
      j = i-1
      while j >=0 and key < arr[j] :
         arr[j+1] = arr[j]
         j -= 1
      arr[j+1] = key
# main
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
   print (arr[i])

出力

The sorted array is:
a
i
l
o
r
t
t
u

時間計算量： O（n * 2）

補助スペース： O（1）

次の図に示すように、すべての変数はグローバルフレームで宣言されます-

結論

この記事では、Python3.xでの挿入ソートとその実装について学びました。またはそれ以前。