[shishirbijalwan]

Hi in this program i have to count the no of comparison made in quicksort. i am able to quicksort the array. but when i am saving the value of comparison in count and then passing this value to totalcomparison=+comparison and then printing total comparison then instead of getting 1 3 6 10 15 i am getting 1 2 3 4 5. pls help
code is

def part(a, left, right): #left and right are the start and end indixes of the subarray
    i = left + 1
    pivot = a[left]# choose first element in subarray as pivot
    j= i+1
    for j in range(left + 1,right+1):
       if a[j] < pivot:
            a[j], a[i] = a[i], a[j]
            i += 1

                  
    pos = i - 1
    a[left], a[pos] = a[pos], a[left]
         
    return pos  #new pivot position. Used to divide the next left and right side of the array.

def quick_sort(a, left, right):
    
 
    if left < right:
        q = part(a, left, right )
        quick_sort(a, left, q - 1)
        quick_sort(a, q + 1, right)
        comparison= right-left
        totalcomparison=+comparison
        print totalcomparison
        
        
        
                    

if __name__=="__main__":                       # If this script is run as a program:
        a = [6,5,4,3,2,1]
        k=0
        left= 0
        right= len(a)-1
        quick_sort(a,left,right)
        print a

This post has been edited by baavgai: 14 February 2013 - 04:43 AM
Reason for edit:: tagged

[baavgai]

This is a compare, right? a[i] < pivot

Instead of doing a comparison with a < operator, pretend you need some kind of function to compare for you. Always use that function to compare. The function will increment a counter. e.g. if cmp(a[i], pivot) < 0:

Note the use of code tags on this site. Python, in particular, is hard to read without them.