Wie verbessere ich meine schnelle Sortierauswahl in Python?

Question

Ich war ursprünglich nur eine einzige zufällige Dreh von

pivots = random.randrange(l,r) 

Hier l und r gegeben mit ganzen Zahlen sein, die meinen Bereich definieren

ich die Laufzeit durch eine starke Erhöhung der wahrscheinlich Haube verbessern wollte, dass mein Pivot wäre ein guter Drehpunkt, indem der Median von drei zufälligen Pivots ausgewählt wird. Unten ist der Code, den ich verwendet habe, und es hat meine Laufzeit um 20% -30% erhöht.

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

Wie kann ich das oben genannte implementieren, um viel schneller zu sein?

Edit: Entire Code hinzugefügt unter

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 

Edit 2: Dies ist der korrigierte Code fällig. Es gab in den Algorithmus ein Fehler zum Aufnehmen der 3 schwenkt

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

Sie könnten die Dreh auf diese Weise wählen:

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] 

Beispiel:

Answer 2

Obwohl es durch zufällige Wahl gelegentlich übertroffen werden kann, es ist immer noch lohnt ein Blick in den median-of-medians Algorithmus für Pivot-Auswahl (und Rangauswahl im Allgemeinen), die läuft in O (n) Zeit. Es ist nicht allzu weit entfernt von dem, was Sie gerade tun, aber es gibt eine stärkere Gewissheit dahinter, dass es einen "guten" Drehpunkt wählt, anstatt nur den Median von drei Zufallszahlen zu nehmen.