以最後一個元素爲轉軸快速排序python

Question

我已經成功測試了我的代碼。它以最後一個元素作爲關鍵點。 但是，當我嘗試數總數沒有。所做的比較，它顯示不正確的計數。 我在計算通過全局變量tot_comparisons。

建議，我哪裏錯了？ 我正在做一些愚蠢的錯誤嗎？

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

我檢查了你的作品快速排序，儘管它在流行的算法給出文本的算法，其中最後一個元素被切換到第一，然後隨之而來的劃分略有不同。這可能會改變對比較次數有影響的排序順序。

例如，你的代碼：基於由OP評論

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 

編輯：

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 

可以切換到。

Answer 2

我建議你在你的腳本的頂部聲明全局變量，檢查此工作基礎的例子：

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