迭代快速排序转vector实现遇问题：代码陷入无限循环

Hey there! Let's figure out why your iterative quicksort implementation with vectors is stuck in an infinite loop. Switching from arrays to vectors can trip up even small logic details, so let's walk through each part of your design and fix those broken bits.

Common Culprits for Infinite Loops in Iterative Quicksort #

1. The getMedian Function Might Be Misordering Elements

A super common issue here is not properly swapping the three elements to ensure left <= med <= right. If the median selection is wrong, your pivot could end up being the smallest or largest element every time, leading to unbalanced partitions and eventually infinite loops (since one side never shrinks).

2. Partition Loop Logic Errors

The partition step is where most infinite loops happen. Common mistakes include:

• Forgetting to increment/decrement your left/right pointers after swapping elements
• Using incorrect loop conditions (like left <= right instead of left < right at the wrong stage)
• Not handling elements equal to the pivot correctly, causing pointers to get stuck

3. Stack Range Management Issues

If you're pushing invalid ranges (like left >= right) onto the stack, or not splitting the partitions correctly after each sort step, the stack will keep reprocessing the same range forever.

Fixed Implementation with Explanations #

Here's a corrected version of your iterative quicksort for vectors, with fixes to each problematic area:

#include <vector>
#include <stack>
#include <algorithm> // For swap

// Adjust left, med, right elements so left <= med <= right
void getMedian(std::vector<int>& vec, int left, int right) {
    int med = left + (right - left) / 2; // Avoid overflow instead of (left+right)/2
    
    // Order left and med
    if (vec[left] > vec[med]) {
        std::swap(vec[left], vec[med]);
    }
    // Order left and right
    if (vec[left] > vec[right]) {
        std::swap(vec[left], vec[right]);
    }
    // Order med and right (now left is smallest, so just need to fix med and right)
    if (vec[med] > vec[right]) {
        std::swap(vec[med], vec[right]);
    }
    // Move median to right-1 position (Hoare's optimization to avoid edge cases)
    std::swap(vec[med], vec[right - 1]);
}

// Partition the vector and return the pivot index
int partition(std::vector<int>& vec, int left, int right) {
    getMedian(vec, left, right);
    int pivot = vec[right - 1]; // Use the median we moved to right-1
    int i = left;
    int j = right - 1;

    while (true) {
        // Move left pointer to first element >= pivot
        while (vec[++i] < pivot);
        // Move right pointer to first element <= pivot
        while (vec[--j] > pivot);
        
        if (i < j) {
            std::swap(vec[i], vec[j]);
        } else {
            break;
        }
    }
    // Swap pivot back to its correct position
    std::swap(vec[i], vec[right - 1]);
    return i;
}

// Iterative quicksort using stack
void quickSort(std::vector<int>& vec) {
    if (vec.size() <= 1) return;

    std::stack<std::pair<int, int>> stk;
    stk.push({0, vec.size() - 1});

    while (!stk.empty()) {
        auto [left, right] = stk.top();
        stk.pop();

        if (left >= right) continue; // Skip invalid ranges

        int pivotIdx = partition(vec, left, right);
        
        // Push larger partition first to optimize stack size (optional but good practice)
        if (pivotIdx - 1 > left) {
            stk.push({left, pivotIdx - 1});
        }
        if (pivotIdx + 1 < right) {
            stk.push({pivotIdx + 1, right});
        }
    }
}

Key Fixes Explained #

• getMedian Adjustments:
  • We calculate the median index safely to avoid integer overflow.
  • We properly order all three elements and move the median to right-1 to avoid edge cases with the first/last elements.
• partition Fixes:
  • We use the median from getMedian as the pivot, which ensures better balance.
  • The loop conditions correctly move pointers past elements that don't need swapping, and we only break when pointers cross.
  • We swap the pivot back to its correct sorted position before returning the index.
• Stack Management:
  • We check if left >= right before processing a range, skipping invalid partitions entirely.
  • We only push valid subranges (where the left boundary is actually less than the right) onto the stack, preventing infinite reprocessing.

How to Debug Further #

If you still run into issues, try adding print statements in the partition function to track the pivot value, left/right indices, and the state of the vector during each step. This will help you spot exactly where the loop is getting stuck (e.g., pointers not moving, or the same range being pushed onto the stack repeatedly).

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