Python
 Computer >> コンピューター >  >> プログラミング >> Python

ヒープソート用のPythonプログラム


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

問題の説明 −配列が与えられたので、ヒープソートの概念を使用して配列を並べ替える必要があります。

ここでは、最大の要素を最後に配置します。これは、配列がソートされるまで繰り返されます。

それでは、以下の実装のソリューションを見てみましょう-

# heapify
def heapify(arr, n, i):
   largest = i # largest value
   l = 2 * i + 1 # left
   r = 2 * i + 2 # right
   # if left child exists
   if l < n and arr[i] < arr[l]:
      largest = l
   # if right child exits
   if r < n and arr[largest] < arr[r]:
      largest = r
   # root
   if largest != i:
      arr[i],arr[largest] = arr[largest],arr[i] # swap
      # root.
      heapify(arr, n, largest)
# sort
def heapSort(arr):
   n = len(arr)
   # maxheap
   for i in range(n, -1, -1):
      heapify(arr, n, i)
   # element extraction
   for i in range(n-1, 0, -1):
      arr[i], arr[0] = arr[0], arr[i] # swap
      heapify(arr, i, 0)
# main
arr = [2,5,3,8,6,5,4,7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
   print (arr[i],end=" ")

出力

Sorted array is
2 3 4 5 5 6 7 8

ヒープソート用のPythonプログラム

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

結論

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


  1. 選択ソート用のPythonプログラム

    この記事では、Python3.xでの選択ソートとその実装について学習します。またはそれ以前。 選択ソート アルゴリズムでは、配列は、ソートされていない部分から最小要素を再帰的に見つけて、それを先頭に挿入することによってソートされます。特定の配列での選択ソートの実行中に、2つのサブ配列が形成されます。 すでにソートされているサブアレイ ソートされていないサブアレイ。 選択ソートを繰り返すたびに、ソートされていないサブアレイの最小要素がポップされ、ソートされたサブアレイに挿入されます。 アルゴリズムの視覚的表現を見てみましょう- それでは、アルゴリズムの実装を見てみましょう- 例

  2. 挿入ソート用の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 &n