Pythonでクイックソートピボット選択を改善するにはどうすればよいですか？

Question

Iもともと私は非常に可能性が高いフードを増やすことで、実行時間を改善したかった

私の範囲を定義する整数になります。ここ

pivots = random.randrange(l,r) 

LとRによって与えられた唯一のランダムなピボットを使用していた私ピボットは、3つのランダムピボットの中央値を選択することによって良好なピボットになります。以下は私が使用したコードで、実行時間が20％〜30％増加しました。

rr = random.randrange 
pivots = [ rr(l,r) for i in range(3) ] 
pivots.sort() 

上記をもっと速く実装するにはどうすればよいですか？

編集：編集2

import random 

def quicksort(array, l=0, r=-1): 
    # array is list to sort, array is going to be passed by reference, this is new to me, try not to suck 
    # l is the left bound of the array to be acte on 
    # r is the right bound of the array to act on 

    if r == -1: 
     r = len(array) 

    # base case 
    if r-l <= 1: 
     return 

    # pick the median of 3 possible pivots 
    #pivots = [ random.randrange(l,r) for i in range(3) ] 
    rr = random.randrange 
    pivots = [ rr(l,r) for i in range(3) ] 
    pivots.sort() 

    i = l+1 # Barrier between below and above piviot, first higher element 
    array[l], array[pivots[1]] = array[pivots[1]], array[l] 

    for j in range(l+1,r): 
     if array[j] < array[l]: 
      array[i], array[j] = array[j], array[i] 
      i = i+1 

    array[l], array[i-1] = array[i-1], array[l] 

    quicksort(array, l, i-1) 
    quicksort(array, i, r) 

    return array 

の下に追加全体コード： これが原因修正されたコードです。それは機会にランダムに選択することによってアウトパフォームすることができますが3つのピボット

import random 

def quicksort(array, l=0, r=-1): 
    # array is list to sort, array is going to be passed by reference, this is new to me, try not to suck 
    # l is the left bound of the array to be acte on 
    # r is the right bound of the array to act on 

    if r == -1: 
     r = len(array) 

    # base case 
    if r-l <= 1: 
     return 

    # pick the median of 3 possible pivots 
    mid = int((l+r)*0.5) 
    pivot = 0 
    #pivots = [ l, mid, r-1] 
    if array[l] > array[mid]: 
     if array[r-1]> array[l]: 
      pivot = l 
     elif array[mid] > array[r-1]: 
      pivot = mid 
    else: 
     if array[r-1] > array[mid]: 
      pivot = mid 
     else: 
      pivot = r-1 

    i = l+1 # Barrier between below and above piviot, first higher element 
    array[l], array[pivot] = array[pivot], array[l] 

    for j in range(l+1,r): 
     if array[j] < array[l]: 
      array[i], array[j] = array[j], array[i] 
      i = i+1 

    array[l], array[i-1] = array[i-1], array[l] 

    quicksort(array, l, i-1) 
    quicksort(array, i, r) 

    return array 

Answer 1

あなたは、このようにピボットを選択できます

alen = len(array) 
pivots = [[array[0],0], [array[alen//2],alen//2], [array[alen-1],alen-1]]] 
pivots.sort(key=lambda tup: tup[0]) #it orders for the first element of the tupla 
pivot = pivots[1][1] 

例：

Answer 2

を選ぶためのアルゴリズムに誤りがありました、それはまだmedian-of-mediansピボット選択のためのアルゴリズム（と一般的には、ランク選別）に探して価値が、どのO（n）時間に実行されます。あなたが現在やっていることから離れているわけではありませんが、3つの乱数の中央値をとるのではなく、「良い」ピボットを選ぶという確固たる裏付けがあります。