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.
def quick_sort(A, start, stop, count):
if start < stop:
# 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.
def main():
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()
This code is giving me this output:
➜ 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 - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
