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

反復クイックソート用のPythonプログラム


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

問題の説明 −配列が与えられたので、反復的な方法を使用したクイックソートの概念を使用して配列をソートする必要があります

ここでは、最初に配列をパーティション化し、別のパーティションを並べ替えて、並べ替えられた配列を取得します。

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

# iterative way
def partition(arr,l,h):
   i = ( l - 1 )
   x = arr[h]
   for j in range(l , h):
      if arr[j] <= x:
         # increment
         i = i+1
         arr[i],arr[j] = arr[j],arr[i]
   arr[i+1],arr[h] = arr[h],arr[i+1]
   return (i+1)
# sort
def quickSortIterative(arr,l,h):
   # Creation of a stack
   size = h - l + 1
   stack = [0] * (size)
   # initialization
   top = -1
   # push initial values
   top = top + 1
   stack[top] = l
   top = top + 1
   stack[top] = h
   # pop from stack
   while top >= 0:
      # Pop
      h = stack[top]
      top = top - 1
      l = stack[top]
      top = top - 1
      # Set pivot element at its correct position
      p = partition( arr, l, h )
      # elements on the left
      if p-1 > l:
         top = top + 1
         stack[top] = l
         top = top + 1
         stack[top] = p - 1
      # elements on the right
      if p+1 < h:
         top = top + 1
         stack[top] = p + 1
         top = top + 1
         stack[top] = h
# main
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSortIterative(arr, 0, n-1)
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