[Tutor] counter not working in Quick Sort script

[Patti Scott via Tutor]

Mac OS 10.10
Python 3.4.3
I self-study Python and am using it for a Coursera algorithm class.

Hi!  My script sorts correctly on all my test arrays. My accumulator variable 
to count the number of comparisons returns nonsense.  I'm counting the (length 
- one) of each sublist that will be sorted in place, not the individual 
comparisons.  I put in a print statement for the count variable, and the 
expected values print, but the function seems to be returning the first 
increment of the count variable instead of the final value.  I reread on the 
difference between print and return, but I haven't figured this out yet.  I 
think I'm doing something language-specific wrong would appreciate another set 
of eyes.


def partition(A, start, stop):
p = A[start] # make pivot first element in partition
i = start + 1
for j in range(i, stop):
# swap elements if A[j] bigger than pivot
if A[j] < p:
A[j], A[i] = A[i], A[j]
i += 1

# swap pivot into sorted index
A[start], A[i-1] = A[i-1], A[start]
return i



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


def main():
unsorted = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
count = quick_sort(unsorted, 0, len(unsorted), 0)
print(unsorted)
print("There are {} comparisons.".format(count))

main()


This code is giving me this output:

➜  algorithms  python3 quick_sort_first.py
7
13
18
22
25
27
28
28
[1, 2, 3, 4, 5, 6, 7, 8]
There are 7 comparisons.

Thank you,
Patricia
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] counter not working in Quick Sort script

[Patti Scott via Tutor]

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