使用带有迭代器的 Hoare 分区进行快速排序时出错，某些特定的小数组出错

Question

我正在尝试使用 Hoare 分区制作 C++ 快速排序算法。但是，我将运行保留在未正确排序的数组中，而大多数数组排序正常。这种令人不安的数组的一个例子是 {1, 3, 0, 4, 3}，它导致 {0, 3, 1, 3, 4}.

代码包含quicksortclass中的Quicksort代码，main函数中的模糊测试


#include <iostream>
#include <random>
#include <vector>

class quicksort
{
public:
    template <class random_access_iterator>
    void operator()(random_access_iterator begin, random_access_iterator end)
    {
        quicksort_recursive_step(begin, end);
    }

private:
    template <class random_access_iterator>
    void quicksort_recursive_step(random_access_iterator begin, random_access_iterator end)
    {
        if ((end - begin) <= 1)
        {
            return;
        }

        auto left = begin;
        auto right = (end - 1);
        const auto pivot = *(left + ((right - left) / 2));

        while (left < right)
        {
            while (*left < pivot)
            {
                left++;
            }

            while (*right > pivot)
            {
                right--;
            }

            if (left < right)
            {
                std::iter_swap(left, right);
                left++;
                right--;
            }
        }

        auto separator = (right + 1);
        quicksort_recursive_step(begin, separator);
        quicksort_recursive_step(separator, end);
    }
};


int main()
{
    std::random_device rd;
    std::mt19937 eng{rd()};
    std::uniform_int_distribution<int> size_dist{0, static_cast<int>(5)};
    quicksort sorter;

    std::vector<int> test = {0, 0, 4, 0, 1};
    sorter(test.begin(), test.end());

    bool has_error = false;

    while (!has_error)
    {
        std::vector<int> test_array(size_dist(rd));
        if (!test_array.empty())
        {
            std::uniform_int_distribution<int> values_dist{0, static_cast<int>(test_array.size() - 1)};
            std::generate(test_array.begin(), test_array.end(), [&values_dist, &rd]() { return values_dist(rd); });
        }
        std::vector<int> original_test_array(test_array);

        std::cout << "Sorting array of size " << test_array.size() << " ... ";
        for (const auto& t : original_test_array)
        {
            std::cout << t << ", ";
        }
        std::cout << std::endl;

        sorter(test_array.begin(), test_array.end());

        bool is_permutation = std::is_permutation(test_array.begin(), test_array.end(), original_test_array.begin());
        bool is_sorted = std::is_sorted(test_array.begin(), test_array.end());

        if (is_permutation && is_sorted)
        {
            std::cout << "OK" << std::endl;
        }
        else
        {
            has_error = true;
            std::cout << "ERROR!" << std::endl;

            std::cout << "Array was: ";
            for (const auto& t : original_test_array)
            {
                std::cout << t << ", ";
            }
            std::cout << std::endl;

            std::cout << "Result is: ";
            for (const auto& t : test_array)
            {
                std::cout << t << ", ";
            }
            std::cout << std::endl;
        }
    }

    return 0;
}

可能的输出（错误在底部）：

Sorting array of size 0 ...
OK
Sorting array of size 2 ... 0, 1,
OK
Sorting array of size 5 ... 1, 2, 2, 0, 0,
OK
Sorting array of size 5 ... 4, 1, 3, 0, 0,
OK
Sorting array of size 5 ... 2, 2, 2, 4, 1,
OK
Sorting array of size 5 ... 1, 3, 3, 3, 1,
OK
Sorting array of size 4 ... 1, 0, 1, 3,
OK
Sorting array of size 1 ... 0,
OK
Sorting array of size 1 ... 0,
OK
Sorting array of size 3 ... 0, 2, 0,
OK
Sorting array of size 4 ... 0, 2, 1, 1,
OK
Sorting array of size 3 ... 0, 1, 1,
OK
Sorting array of size 4 ... 3, 1, 3, 1,
OK
Sorting array of size 4 ... 3, 2, 3, 3,
OK
Sorting array of size 2 ... 0, 0,
OK
Sorting array of size 4 ... 3, 3, 3, 1,
OK
Sorting array of size 3 ... 0, 2, 0,
OK
Sorting array of size 3 ... 0, 0, 2,
OK
Sorting array of size 1 ... 0,
OK
Sorting array of size 5 ... 2, 3, 4, 1, 3,
OK
Sorting array of size 3 ... 1, 1, 0,
OK
Sorting array of size 3 ... 1, 0, 2,
OK
Sorting array of size 3 ... 1, 0, 2,
OK
Sorting array of size 1 ... 0,
OK
Sorting array of size 4 ... 0, 3, 3, 3,
OK
Sorting array of size 0 ...
OK
Sorting array of size 5 ... 4, 1, 3, 1, 0,
OK
Sorting array of size 3 ... 2, 2, 1,
OK
Sorting array of size 0 ...
OK
Sorting array of size 2 ... 1, 1,
OK
Sorting array of size 0 ...
OK
Sorting array of size 2 ... 0, 1,
OK
Sorting array of size 2 ... 0, 1,
OK
Sorting array of size 2 ... 0, 0,
OK
Sorting array of size 5 ... 3, 0, 0, 3, 3,
OK
Sorting array of size 3 ... 0, 1, 2,
OK
Sorting array of size 2 ... 1, 0,
OK
Sorting array of size 3 ... 0, 2, 1,
OK
Sorting array of size 3 ... 1, 1, 0,
OK
Sorting array of size 0 ...
OK
Sorting array of size 4 ... 0, 3, 0, 2,
OK
Sorting array of size 0 ...
OK
Sorting array of size 2 ... 0, 0,
OK
Sorting array of size 0 ...
OK
Sorting array of size 1 ... 0,
OK
Sorting array of size 0 ...
OK
Sorting array of size 5 ... 4, 0, 1, 1, 3,
OK
Sorting array of size 0 ...
OK
Sorting array of size 5 ... 1, 3, 0, 4, 3,
ERROR!
Array was: 1, 3, 0, 4, 3,
Result is: 0, 3, 1, 3, 4,

如何解决这个错误？每次我尝试解决它时，我都会破坏其他东西。我也找不到结合 Hoare 分区和迭代器的好例子，因为 Lomuto 分区主要用于教育文献。我也想避免使用 std::partition 等

Answer 1

一个典型的 post-increment 和 post-decrement 版本的 Hoare 分区方案类似于问题中使用的，必须补偿右索引可能在下面递减的可能性数组的开头。

作为替代方案，此示例代码使用 Hoare 分区方案的预递增和预递减版本，除了它跳过递减然后递增左侧（下面代码中的 b）迭代器，使用 goto 跳转进入两个分区循环的中间。我可以更改代码以避免转到，但优化编译器可能会像我的源代码中的转到一样进行编译。对于偶数个元素，它使用左中间元素作为主元 (p = *(b+(e-b-1)/2)).

#include <iostream>
#include <iterator>
#include <vector>

void QuickSort(std::vector<int>::iterator b, std::vector<int>::iterator e)
{
std::vector<int>::iterator i = b;
std::vector<int>::iterator j = e;
int p = *(b+(e-b-1)/2);
    if((e-b) < 2)
        return;
    if(*i >= p)
        goto loop0;
    while(1){
        while (*(++i) < p);
loop0:
        while (*(--j) > p);
        if (i >= j)
            break;
        std::swap(*i, *j);
    }
    j++;
    QuickSort(b, j);
    QuickSort(j, e);
}

int rnd32()                     /* random number */
{
static unsigned int r = 0u;
    r = r * 1103515245u + 12345u;
    return (int)r;
}

#define COUNT (1024)

int main(int argc, char**argv)
{
size_t i;
    std::vector <int> a(COUNT);
    for(i = 0; i < COUNT; i++)
        a[i] = rnd32();
    QuickSort(a.begin(), a.end());
    for(i = 1; i < COUNT; i++){
        if(a[i-1] > a[i])
            break;
    }
    if(i == COUNT)
        printf("passed\n");
    else
        printf("failed\n");
    return(0);
}

Answer 2

我找到了我自己的问题的答案。在我的代码中，当左右迭代器交换然后相互交叉时，我结束了我的 while 循环。因此，它是 swap(lef,right)、left++、right-- 和 stop。但是，该算法应该再次执行 while(*left < pivot){left++;} 和 while (*right > pivot){right--;} 循环以将分隔符设置在正确的位置。在查看 CLRS 的伪代码时，这对我来说并不是很明显，但是 while 循环也在 return.

之前再次执行

HOARE-PARTITION(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while TRUE
        repeat
            j = j - 1
        until A[j] <= x
        repeat
            i = i + 1
        until A[i] >= x
        if i < j
            exchange A[i] with A[j]
        else 
            return j

正确的代码是：

template <class T>
class quicksort
{
public:
    template <class random_access_iterator>
    void operator()(random_access_iterator begin, random_access_iterator end)
    {
        quicksort_recursive_step(begin, end);
    }

private:
    template <class random_access_iterator>
    void quicksort_recursive_step(random_access_iterator begin, random_access_iterator end)
    {
        assert(begin <= end);

        if ((end - begin) <= 1)
        {
            return;
        }

        auto left = begin;
        auto right = (end - 1);
        auto middle = (left + ((right - left) / 2));
        const auto pivot = *middle;

        while (*left < pivot)
        {
            left++;
        }

        while (*right > pivot)
        {
            right--;
        }

        while (left < right)
        {
            std::iter_swap(left, right);

            left++;
            while (*left < pivot)
            {
                left++;
            }

            right--;
            while (*right > pivot)
            {
                right--;
            }
        }
        
        auto bound = (right + 1);
        quicksort_recursive_step(begin, bound);
        quicksort_recursive_step(bound, end);
    }
};

使用带有迭代器的 Hoare 分区进行快速排序时出错，某些特定的小数组出错

Error in quicksort using Hoare partitioning with iterators, error with some specific small arrays

c++

sorting

iterator

quicksort