# counting coparison in quicksort

Page 1 of 1

## 1 Replies - 1020 Views - Last Post: 14 February 2013 - 04:49 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=312212&amp;s=713686e0980233a8e06747755527ec1d&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 shishirbijalwan

Reputation: 0
• Posts: 1
• Joined: 14-February 13

# counting coparison in quicksort

Posted 14 February 2013 - 04:23 AM

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

Is This A Good Question/Topic? 0

## Replies To: counting coparison in quicksort

### #2 baavgai

• Dreaming Coder

Reputation: 6054
• Posts: 13,107
• Joined: 16-October 07

## Re: counting coparison in quicksort

Posted 14 February 2013 - 04:49 AM

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.