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

问题描述

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

)进行传递

例如：当我让此算法对包含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)

---

解决方案

给定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]

我将首先从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现在返回(comp, swap, j)的3元组，因此我们需要相应地调整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返回一个二元组(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返回值，因此请确保将其存储到变量或printprint

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]