バイナリ挿入ソート用のPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 −配列が与えられたので、バイナリ挿入ソートの概念を使用して配列をソートする必要があります。

ここでは、名前が示すように、挿入ソートアルゴリズムとともにバイナリ検索の概念を使用します。

次に、以下の実装のソリューションを見てみましょう-

例

# sort
def insertion_sort(arr):
   for i in range(1, len(arr)):
      temp = arr[i]
      pos = binary_search(arr, temp, 0, i) + 1
      for k in range(i, pos, -1):
         arr[k] = arr[k - 1]
      arr[pos] = temp
def binary_search(arr, key, start, end):
   #key
   if end - start <= 1:
      if key < arr[start]:
         return start - 1
      else:
         return start
   mid = (start + end)//2
   if arr[mid] < key:
      return binary_search(arr, key, mid, end)
   elif arr[mid] > key:
      return binary_search(arr, key, start, mid)
   else:
      return mid
# main
arr = [1,5,3,4,8,6,3,4]
n = len(arr)
insertion_sort(arr)
print("Sorted array is:")
for i in range(n):
   print(arr[i],end=" ")

出力

Sorted array is :
1 3 3 4 4 5 5 6 8

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、バイナリ挿入ソート用のPythonプログラムを作成する方法について学びました