[Tutor] counter not working in Quick Sort script

[Alan Gauld]

On 29/10/15 19:11, Patti Scott via Tutor wrote:

Caveat: I didn't check the algorithms for correctness,
I'll just take your word for that.

My accumulator variable to count the number of comparisons returns nonsense.
# increment count by length of partition less the pivot
count += (stop - start - 1)
print(count)
split = partition(A, start, stop)
# recursively sort lower partition
quick_sort(A, start, split-1, count)
# recursively count upper partition
quick_sort(A, split, stop, count)
return count

Notice that you only set count once at the top of the function.
What the recursive instances of the function do is irrelevant
because you don't use their return values. So the return value
of this function is always (count + stop - start -1) for the
initial invocation value of count.

I suspect you really want to do something to count based on
the returns from the recursive calls too.

unsorted = [ 1, 2, 3, 4, 5, 6, 7, 8 ]

This looks very sorted to me? Is that correct?

count = quick_sort(unsorted, 0, len(unsorted), 0)

count should return 0+len()-0-1 -> len-1 = 7

print(unsorted)
print("There are {} comparisons.".format(count))
main()
➜ algorithms python3 quick_sort_first.py
7

This is the outer functions count

13
18
22
25
27
28
28

These are the recursive values of count which are
invisible to the outer invocation

[1, 2, 3, 4, 5, 6, 7, 8]

This is the sorted result

There are 7 comparisons.

And this reflects the outer value of count again.

Your code does exactly what you told it to do.
Your problem is that you are not using the returned
counts from the recursive calls.
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos


_______________________________________________
Tutor maillist - ***@python.org
To unsubscribe or change subscription options:
https://ma