Pythonクイックソート

クイックソートは、分割統治法（Divide and conquer）を使用して、シーケンス（list）を2つのより小さいサブシーケンスとより大きいサブシーケンスに分割し、2つのサブシーケンスを再帰的にソートします。

ステップは次のとおりです。

• ベンチマーク値の選択：シリーズから要素を選択し、「ピボット」（pivot）と呼ばれます。
• 分割：シーケンスを再ソートします。ピボット値よりも小さいすべての要素はピボットの前に配置され、ピボット値よりも大きいすべての要素はピボットの後ろに配置されます（ピボットに等しい数はどちらの側にも配置できます）。分割が終了した後、ピボット値のソートが終わりです。
• サブシーケンスを再帰的に並べ替える：ピボット値よりも小さい要素のサブシーケンスと、ピボット値よりも大きい要素のサブシーケンスを再帰的に並べ替えます。

再帰の最下位の判断条件は、シーケンスのサイズが0または1であるということです。この時点で、シーケンスは明らかにすでに順序付けられています。

ピボット値を選択するためのいくつかの特定の方法があり、この選び方は、ソートの速度に決定的な影響を及ぼします。

実例

def partition(arr,low,high): 
    i = ( low-1 )         # 最小の要素インデックス
    pivot = arr[high]     
  
    for j in range(low , high): 
  
　　 # 現在の要素はpivot以下である
        if   arr[j] <= pivot: 
          
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 
  
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 

# arr[] --> 配列を並べ替える
# low  --> インデックスの開始
# high  --> インデックスの終了
  
# クイックソート関数

def quickSort(arr,low,high): 
    if low < high: 
  
        pi = partition(arr,low,high) 
  
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 
  
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 
print ("ソートされた配列:") 
for i in range(n): 
    print ("%d" %arr[i]),

上記のコードを実行した結果は次のとおりです。

ソートされた配列：
1
5
7
8
9
10