如何修改混合快速排序代码以分别测试插入排序与纯快速排序的运行时间

Let's fix your test code so you can get accurate runtime comparisons. The core problems with your current setup are:

1. You're reusing the same array for both tests—after the first call to quickSort, the array is already sorted, so the second run doesn't reflect the real runtime of sorting an unsorted array.
2. Your mixed quickSort function will always use insertion sort for 500-element arrays (since 500 < 501), so you can't trigger pure quicksort with it as-is.

Solution 1: Use Separate Array Copies + a Pure Quicksort Function #

The cleanest approach is to create two identical unsorted arrays, and implement a dedicated pure quicksort function that skips the insertion sort branch entirely.

Here's the revised code:

import time
import random

# Your existing helper functions
def insert_sort(A, p, r):
    for i in range(p+1, r+1):
        key = A[i]
        j = i - 1
        while j >= p and A[j] > key:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = key

def partition(A, p, r):
    pivot = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i

# Original hybrid quicksort
c = 501
def hybrid_quickSort(A, p, r):
    if p < r:
        m = r - p + 1
        if m < c:
            insert_sort(A, p, r)
        else:
            q = partition(A, p, r)
            hybrid_quickSort(A, p, q)
            hybrid_quickSort(A, q + 1, r)

# Pure quicksort (no insertion sort fallback)
def pure_quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        pure_quickSort(A, p, q)
        pure_quickSort(A, q + 1, r)

# Test setup
# Generate two identical unsorted arrays
unsorted_array = [random.randint(0, 10000) for _ in range(500)]
array_for_insert = unsorted_array.copy()
array_for_quicksort = unsorted_array.copy()

# Test insertion sort (triggered via hybrid quicksort)
start = time.time()
hybrid_quickSort(array_for_insert, 0, 499)
end = time.time()
insert_runtime = end - start

# Test pure quicksort
start1 = time.time()
pure_quickSort(array_for_quicksort, 0, 499)
end1 = time.time()
quicksort_runtime = end1 - start1

# Print results
print("Number of elements: 500")
print(f"Insertion Sort Runtime: {insert_runtime:.6f} seconds")
print(f"Pure Quicksort Runtime: {quicksort_runtime:.6f} seconds")

Solution 2: Temporary Threshold Adjustment (No New Function Needed) #

If you don't want to write a separate pure quicksort function, you can temporarily lower the threshold c to force the hybrid function to use quicksort for 500-element arrays. Just remember to restore the original threshold afterward:

# Test pure quicksort via threshold adjustment
array_for_quicksort_alt = unsorted_array.copy()
start2 = time.time()

# Temporarily change threshold to 499 (so 500 >= c triggers quicksort)
original_c = c
c = 499
hybrid_quickSort(array_for_quicksort_alt, 0, 499)
c = original_c  # Restore original threshold

end2 = time.time()
quicksort_runtime_alt = end2 - start2
print(f"Pure Quicksort Runtime (Threshold Hack): {quicksort_runtime_alt:.6f} seconds")

Key Fixes Explained #

• Separate Arrays: By using .copy() to create identical unsorted arrays, both tests run on the same initial data—no more skewed results from sorting an already ordered array.
• Pure Quicksort Function: This eliminates the insertion sort fallback entirely, ensuring you're measuring the true runtime of standard quicksort on an unsorted 500-element array.
• Threshold Adjustment: A quick workaround if you want to reuse your existing hybrid function without rewriting it.

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