That make sense, thank you. I changed the quick_sort() to
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
left = quick_sort(A, start, split-1, count)
if left:
count = left
# recursively count upper partition
right = quick_sort(A, split, stop, count)
if right:
count = right
return count
Yes, the sorting worked on all the *lists I tested.* For counting comparisons,
I used a sorted list with a known number of comparisons to be able check the
accumulator variable.
-Patricia
--------------------------------------------
On Thu, 10/29/15, Alan Gauld <alan.ga...@btinternet.com> wrote:
Subject: Re: [Tutor] counter not working in Quick Sort script
To: tutor@python.org
Date: Thursday, October 29, 2015, 9:12 PM
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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
