在快速排序(Python)中计算交换和比较

Question

我正在尝试在快速排序中计算交换和比较操作。 我想我在正确的位置设置了计数器，但由于递归，我从来没有为这些值获得正确的数量。为了在整个递归过程中"存储"值，我将它们作为参数(qui_swap和qui_comp移交。

例如：当我让这个算法对包含 500 个整数的列表进行排序时，它会返回 120 个交换和 1 个比较。

下面是我的代码：

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)

Answer 1

快速排序返回计数器的更新值。但是你不分配它们。

快速排序函数的最后 5 行应该是：

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

(您还需要将裸返回更改为：

if end_index <= start_index:  
return(qui_swap, qui_comp)

Answer 2

给定霍尔的快速排序算法 -

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]

我将首先从partition函数开始，并包括comp和swap计数器 -

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现在返回 3 元组的(comp, swap, j)，因此我们需要相应地调整quicksort-

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)

为了让调用方接收这些信息，我们必须格式化quicksort的返回值。我们可以从返回(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

但这仅包括第一遍的比较和交换计数器。 现在我们知道quicksort返回一个 2 元组(comp, swap)我们也可以从递归调用中获取这些

元组 -

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

目前quicksort在if分支下只有一个返回值，除此之外它隐式返回None。在这种情况下，我们需要提供空comp和swap计数器 -

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

我们完成了！我们的新quicksort返回一个值，因此请确保将其存储到变量中或print它 -

x = [5,0,9,7,4,2,8,3,1,6]
print(quicksort(x, 0, len(x)-1))
print(x)

结果-

(31, 9)                          # 31 comparisons, 9 swaps
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]   # sorted result

现在x已排序。如果我们重复quicksort，我们会得到不同的比较和交换计数器 -

print(quicksort(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

对于小阵列，我们可以更轻松地验证结果 -

y = [2,1,3]
print(quicksort(y, 0, len(y)-1))
print(y)

(3, 1)                           # 3 comparisons, 1 swap 
[1, 2, 3]                        # sorted result

---

如果您在程序中逐行编辑时遇到问题，这里有一个完整的工作版本 -

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)
def partition(A, lo, hi):
comp = 0
swap = 0
pivot = A[(hi + lo) // 2]
i = lo
j = hi
while True:
while A[i] < pivot:
comp += 1
i += 1
while A[j] > pivot:
comp += 1
j -= 1
if i >= j:
return (comp, swap, j)
swap += 1
A[i], A[j] = A[j], A[i]

x = [5,0,9,7,4,2,8,3,1,6]
print(quicksort(x, 0, len(x)-1))
print(x)
print(quicksort(x, 0, len(x)-1))
print(x)

(31, 9)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
(25, 0)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

y = [2,1,3]
print(quicksort(y, 0, len(y)-1))
print(y)

(3, 1)
[1, 2, 3]