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

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

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

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

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

例

# divide function
def partition(arr,low,high):
   i = ( low-1 )
   pivot = arr[high] # pivot element
   for j in range(low , high):
      # If current element is smaller
      if arr[j] <= pivot:
         # increment
         i = i+1
         arr[i],arr[j] = arr[j],arr[i]
   arr[i+1],arr[high] = arr[high],arr[i+1]
   return ( i+1 )
# sort
def quickSort(arr,low,high):
   if low < high:
      # index
      pi = partition(arr,low,high)
      # sort the partitions
      quickSort(arr, low, pi-1)
      quickSort(arr, pi+1, high)
# main
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSort(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

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

結論

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