I'm trying to count the swapping and comparison operations in a quicksort. I think I set the counters at the right locations, but due to the recursion, I never get the right amount for these values. To 'store' the values throughout the recursion I hand them over as parameters(qui_swap and qui_comp.
For example: When I let this algorithm sort a list with 500 integers, it returns 120 swaps and 1 comparison.
Below is my code:
qui = quicksort(numbers, 0, len(numbers)-1, 0, 0)
def partition(numbers, start_index, end_index, qui_swap):
# Select the middle value as the pivot.
midpoint = start_index (end_index - start_index) // 2
pivot = numbers[midpoint]
# "low" and "high" start at the ends of the list segment
# and move towards each other.
low = start_index
high = end_index
done = False
while not done:
# Increment low while numbers[low] < pivot
while numbers[low] < pivot:
low = low 1
# Decrement high while pivot < numbers[high]
while pivot < numbers[high]:
high = high - 1
# If low and high have crossed each other, the loop
# is done. If not, the elements are swapped, low is
# incremented and high is decremented.
if low >= high:
done = True
else:
temp = numbers[low]
numbers[low] = numbers[high]
numbers[high] = temp
low = 1
high -= 1
qui_swap = 1
# "high" is the last index in the left segment.
return (high, qui_swap)
def quicksort(numbers, start_index, end_index, qui_swap, qui_comp):
# Only attempt to sort the list segment if there are
# at least 2 elements
if end_index <= start_index:
return
# Partition the list segment
#count comparisons here
qui_comp = 1
high = partition(numbers, start_index, end_index,qui_swap)
qui_swap = high[1]
# Recursively sort the left segment
quicksort(numbers, start_index, int(high[0]), qui_swap, qui_comp 1)
# Recursively sort the right segment
quicksort(numbers, int(high[0]) 1, end_index, qui_swap, qui_comp 1)
return(qui_swap, qui_comp)
CodePudding user response：
Your quicksort returns the updated values of your counters. But you don't assign them.
The last 5 lines of your quicksort function should be :
# Recursively sort the left segment
l_swap, l_comp = quicksort(numbers, start_index, int(high[0]), qui_swap, qui_comp 1)
# Recursively sort the right segment
r_swap, r_comp = quicksort(numbers, int(high[0]) 1, end_index, qui_swap, qui_comp 1)
qui_swap = l_swap r_swap
qui_comp = l_comp r_comp
return(qui_swap, qui_comp)
(and you will also need to change the bare return to this:
if end_index <= start_index:
return(qui_swap, qui_comp)
CodePudding user response：
Given Hoare's quicksort algorithm -
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
p = partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p 1, hi)
def partition(A, lo, hi):
pivot = A[(hi lo) // 2]
i = lo
j = hi
while True:
while A[i] < pivot:
i = 1
while A[j] > pivot:
j -= 1
if i >= j:
return j
A[i], A[j] = A[j], A[i]
I would first start with the partition function and include comp and swap counters -
def partition(A, lo, hi):
comp = 0 # comparison counter
swap = 0 # swap counter
pivot = A[(hi lo) // 2]
i = lo
j = hi
while True:
while A[i] < pivot:
comp = 1 # increase comparison count
i = 1
while A[j] > pivot:
comp = 1 # increase comparison count
j -= 1
if i >= j:
return (comp, swap, j) # return comp, swap, and j
swap = 1 # increase swap count
A[i], A[j] = A[j], A[i]
partition now returns a 3-tuple of (comp, swap, j) so we need to adjust quicksort accordingly -
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
(comp, swap, p) = partition(A, lo, hi) # receive 3-tuple
quicksort(A, lo, p)
quicksort(A, p 1, hi)
In order for the caller to receive these infos, we have to format quicksort's return value. We can start by returning (comp, swap) -
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
(comp, swap, p) = partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p 1, hi)
return (comp, swap) # return comp, swap
But that only includes the comparison and swap counters for the first pass. Now that we know quicksort returns a 2-tuple (comp, swap) we can get those from the recursive calls too -
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
(comp, swap, p) = partition(A, lo, hi)
(lcomp, lswap) = quicksort(A, lo, p) # left comp, swap
(rcomp, rswap) = quicksort(A, p 1, hi) # right comp, swap
return (comp lcomp rcomp, swap lswap rswap) # sum comp, swap
Currently quicksort only has a return value under the if branch, outside of that it implicitly returns None. We need to provide the empty comp and swap counters in this case -
def quicksort(A, lo, hi):
if lo >= 0 and hi >= 0 and lo < hi:
(comp, swap, p) = partition(A, lo, hi)
(lcomp, lswap) = quicksort(A, lo, p)
(rcomp, rswap) = quicksort(A, p 1, hi)
return (comp lcomp rcomp, swap lswap rswap)
return (0,0) # base case, return empty counters
And we're done! Our new quicksort returns a value, so make sure to store it to a variable or print it -
x = [5,0,9,7,4,2,8,3,1,6]
print(quicksort(x, 0, len(x)-1))
print(x)
Result -
(31, 9) # 31 comparisons, 9 swaps
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # sorted result
Now x is sorted. If we repeat the quicksort, we get different comparison and swap counters -
print(quicksort_stat(x, 0, len(x)-1))
print(x)
(25, 0) # 25 comparisons, 0 swaps
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # sorted result
And for small arrays, we can verify the result more easily -
y = [2,1,3]
print(quicksort_stat(y, 0, len(y)-1))
print(y)
(3, 1) # 3 comparisons, 1 swap
[1, 2, 3] # sorted result