[Tutor] counter not working in Quick Sort script

[Patti Scott]

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.gauld at btinternet.com> wrote:

 Subject: Re: [Tutor] counter not working in Quick Sort script
 To: tutor at 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 at python.org
 To unsubscribe or change subscription
 options:
 https://mail.python.org/mailman/listinfo/tutor