为Quick Sort算法添加swap计数器出现错误结果，寻求解决方法

Hey there! Let's figure out why your swap counter is giving an incorrect value (14) for your 128-element array. A count that low almost always means your counter isn't being updated in every spot where a swap actually occurs in your Quick Sort implementation. Let's break down the most common pitfalls and how to fix them:

Common Mistakes to Check #

• Forgetting to count swaps in the partition function: The partition step is where most swaps happen in Quick Sort. If you're only incrementing the counter in the recursive calls (and not in the partition logic itself), you're missing the vast majority of swaps. For example, in the Lomuto partition scheme, every time you swap arr[i] and arr[j] when arr[j] is less than or equal to the pivot, you need to bump the counter by 1.
• Skipping the final pivot swap: Most partition implementations end by swapping the pivot element into its correct sorted position. This is a valid swap and needs to be counted too—don't overlook this step!
• Passing the counter by value instead of reference: If you're passing the counter as a regular variable (not a reference/pointer or mutable object), changes made inside recursive calls won't persist back to the main counter. For example, in Python, using a list to hold the counter (like counter = [0]) lets you modify its value across recursive calls since lists are mutable.
• Accidentally resetting the counter: Double-check that you aren't reinitializing the counter anywhere in your recursive logic—this would erase all previous counts and give you a wrong number.

Example Implementation with Correct Swap Counting #

Here's a Python Quick Sort example that properly tracks swap counts, using a mutable list to preserve the counter across recursion:

def quick_sort_with_swap_count(arr):
    swap_counter = [0]  # Mutable list to track count across recursion

    def partition(low, high):
        pivot = arr[high]
        i = low - 1  # Index of smaller element
        for j in range(low, high):
            # If current element is <= pivot
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
                swap_counter[0] += 1  # Count this swap
        # Swap pivot to its correct position
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        swap_counter[0] += 1  # Don't forget this final swap
        return i + 1

    def sort_helper(low, high):
        if low < high:
            pi = partition(low, high)
            sort_helper(low, pi - 1)
            sort_helper(pi + 1, high)

    sort_helper(0, len(arr) - 1)
    return swap_counter[0]

# Test with your array
your_arr = [1.960, 2.010, 2.020, 1.940, 2.030, 2.050, 2.000, 1.890, 1.860, 1.960, 1.990, 2.010, 2.010, 2.010, 1.960, 1.940, 1.920, 1.930, 1.980, 1.960, 1.940, 1.900, 1.860, 1.890, 1.860, 1.860, 1.820, 1.810, 1.790, 1.750, 1.780, 1.850, 1.790, 1.790, 1.780]  # Add the rest of your 128 elements here
total_swaps = quick_sort_with_swap_count(your_arr)
print(f"Total swaps performed: {total_swaps}")

Final Checks #

Go through your existing code line by line:

• Mark every instance where two elements in the array are swapped
• Ensure each of these instances has a counter += 1 (or equivalent) line
• Verify that your counter is being modified in place (not copied) so all recursive calls update the same value

内容的提问来源于stack exchange，提问作者user7468934