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

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

アルゴリズム

1. Iterate over the input elements by growing the sorted array at each iteration.
2. Compare the current element with the largest value available in the sorted array.
3. If the current element is greater, then it leaves the element in its place 
   and moves on to the next element else it finds its correct position in the 
   sorted array and moves it to that position in the array.
4. This is achieved by shifting all the elements towards the right, which are 
   larger than the current element, in the sorted array to one position ahead.

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

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

例

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での挿入ソートとその実装について学びました。またはそれ以前。