Quick Sort in Python mit dem letzten Element als Pivot

Question

Ich habe meinen Code erfolgreich getestet. Es arbeitet mit dem letzten Element als Pivot. Allerdings, wenn ich versuche, die Gesamtzahl no. der vorgenommenen Vergleiche zeigt es eine falsche Zählung. Ich zähle durch die globale Variable tot_comparisons.

Vorschläge, wo liege ich falsch? Gibt es einen dummen Fehler, den ich mache?

def swap(A,i,k): 
    temp=A[i] 
    print "temp is " 
    print temp 
    A[i]=A[k] 
    A[k]=temp 

def partition(A,start,end): 
    pivot=A[end] 
    pivot_index=start 
    #pivot=A[end] 


    for i in range(start,end): 

     #if A[i]<=pivot: 
     if A[i]<pivot: 
      print 'HHHHHHHHHHHHHhh' 
      swap(A,i,pivot_index) 
      pivot_index+=1 
    #swap(A,pivot_index,end) 
    swap(A,pivot_index,end) 
    return pivot_index 

def quicksort(A,start,end): 
    global tot_comparisons 
    if start<end: 

     pivot_index=partition(A,start,end) 
     tot_comparisons+=end-start 
     print "pivot_index" 
     print pivot_index 
     print "ENDS" 


     quicksort(A, start,pivot_index-1) 

     #tot_comparisons+=end-pivot_index 
     #quicksort(A, pivot_index, end) 

     quicksort(A, pivot_index+1, end) 

#A=[45,21,23,4,65] 

#A=[21,23,19,22,1,3,7,88,110] 
#A=[1,22,3,4,66,7] 

#A=[1, 3, 7, 19, 21, 22, 23, 88, 110] 
#A=[7,2,1,6,8,5,3,4] 

temp_list=[] 
f=open('temp_list.txt','r') 
for line in f: 
    temp_list.append(int(line.strip())) 
f.close() 
print 'list is ' 
#print temp_list 
print 'list ends' 

tot_comparisons=0 
#quicksort(A, 0, 7) 
quicksort(temp_list, 0, 9999) 
#quicksort(temp_list, 0, len(temp_list)) 
print 'hhh' 
print temp_list 
print tot_comparisons 
#print A 

Answer 1

Ich habe, dass Ihr quicksort funktioniert, obwohl es aus dem Algorithmus gegeben in der populären algorithmischen Texten etwas anders ist, in dem das letzte Element mit dem ersten geschaltet wird und dann die Partitionierung erfolgt. Dies kann die Reihenfolge der Sortierung ändern, die sich auf die Anzahl der Vergleiche auswirkt.

Beispiel: Ihr Code:

def partition(A,start,end): 
    swap(A,start,end) 
    pivot=A[start] 
    pivot_index=start + 1 
    for i in range(start+1,end+1): 
     if A[i] < pivot: 
      swap(A,i,pivot_index) 
      pivot_index+=1 
    swap(A,pivot_index-1,start) 
    return pivot_index-1 

Herausgegeben von OP basierend auf Kommentar:

def partition(A,start,end): 
    pivot=A[end] 
    pivot_index=start 
    for i in range(start,end): 
     if A[i] < pivot: 
      swap(A,i,pivot_index) 
      pivot_index+=1 
    swap(A,pivot_index,end) 
    return pivot_index 

kann umgeschaltet werden.

Answer 2

Ich würde vorschlagen, Sie globalen Variable am Anfang des Skripts zu erklären, diesen Arbeitsgrund Beispiel überprüfen:

inside = 0 
def qsort(l): 
    global inside 
    inside += 1 
    if len(l) <= 1: 
     return l 
    pivot = l[-1] 
    return qsort(filter(lambda x: x < pivot, l[:-1])) + [pivot] + qsort(filter(lambda x: x >= pivot, l[:-1])) 

import random 
l = [random.randint(0,100) for _ in xrange(100)] 
print qsort(l) 
print inside 

>>> [1, 1, 2, 3, 7, 9, 10, 11, 11, 11, 13, 13, 13, 13, 17, 17, 17, 18, 18, 21, 22, 23, 26, 26, 28, 30, 30, 32, 32, 34, 35, 38, 40, 41, 42, 42, 42, 42, 43, 44, 45, 46, 47, 47, 48, 48, 49, 51, 51, 54, 55, 56, 56, 56, 58, 59, 60, 60, 61, 61, 62, 63, 65, 67, 67, 68, 68, 70, 70, 72, 73, 74, 77, 79, 80, 83, 85, 85, 85, 86, 87, 89, 90, 90, 90, 91, 91, 95, 96, 96, 96, 97, 97, 97, 98, 98, 98, 99, 99, 99] 
>>> 135