[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.

> 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