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
