应用于对象指针向量的快速排序 - 无限循环

Question

我不明白为什么算法会导致无限循环。我正在尝试根据最终价格对向量进行排序。支点始终保持不变。也许问题在于对象的交换

Motorbike findPivotPricee(vector<Motorbike*>& available, int left, int right)
{
    int center = (left + right) / 2;

    if (available[center]->finalPrice() < available[left]->finalPrice())
    {
        swap(*available[left], *available[center]);
    }

    if (available[right]->finalPrice()< available[left]->finalPrice())
    {
        swap(*available[left], *available[right]);
    }

    if (available[right]->finalPrice() < available[center]->finalPrice())
    {
        swap(*available[center], *available[right]);
    }

    Motorbike pivot = *available[center];

    swap(*available[center], *available[right - 1]);

    return pivot;

}

void quickSortMotorbikeByPrice(vector<Motorbike*>& available, int left, int right)
{
    int i = left;
    int j = right-1;

    Motorbike pivot = findPivotPricee(available, left, right);
    cout << pivot.finalPrice() << endl;

    while (i < j)
    {
        while (available[i]->finalPrice() < pivot.finalPrice())
        {
            i++;
        }

        while (available[j]->finalPrice() > pivot.finalPrice())
        {
            j--;
        }

        if (i <= j)
        {
            swap(*available[i], *available[j]);
            i++;
            j--;
        }
        else {
            break;
        }
    }

    swap(*available[i], *available[right - 1]);//restore the pivot

    if (left < right) {
        if (left<j) quickSortMotorbikeByPrice(available, left, j);
        if (right>i) quickSortMotorbikeByPrice(available, i, right);
    }
}

void quickSortMotorbikeByPrice(vector<Motorbike*>& available)
{
    quickSortMotorbikeByPrice(available, 0, available.size() - 1);
}

Answer 1

通常，来自维基百科的算法，例如the quicksort algorithms 很难转换为有效的实现，因为它们未能指出给定算法隐含的假定编程模型。例如，如果它是基于 0 或基于 1 的数组，并且他们假设使用的索引是有符号整数而不是无符号整数。

然后，人们开始尝试使用这些算法，例如在 C++ 和运行中解决各种问题。相当浪费时间...而且通过查看问题中给出的代码，我认为问题的作者试图使用来自维基百科的信息...

因为这显然是作业，打动你的老师并使用下面的代码。快速排序很难正确，可能需要很长时间才能确定您是否应该写 lo = left + 1 或 lo = left 等

#include <cstdint>
#include <memory>
#include <vector>
#include <iostream>
#include <cassert>

template <class X>
void vswap(std::vector<X>& v, size_t i1, size_t i2)
{
    X temp = v[i1];
    v[i1] = v[i2];
    v[i2] = temp;
}

template <typename X>
std::ostream& operator<<(std::ostream& stm, const std::vector<X>& v)
{
    stm << "[|";
    size_t i = 0;
    for (auto& x : v)
    {
        if (0 == i)
            stm << x;
        else
            stm << "; " << x;
        i++;
    }
    stm << "|]";
    return stm;
}

template <typename X>
std::ostream& operator<<(std::ostream& stm, const std::vector<X*>& v)
{
    stm << "[|";
    size_t i = 0;
    for (auto& x : v)
    {
        if (0 == i)
            if (nullptr == x) stm << "nullptr"; else stm << *x;
        else
            if (nullptr == x) stm << "; nullptr"; else stm << "; " << *x;
        i++;
    }
    stm << "|]";
    return stm;
}

template <class X, class Predicate>
size_t partition(std::vector<X> & v, Predicate p, size_t left, size_t right)
{
    size_t boundary = left;
    X x = v[boundary];
    for (size_t i = left; i < right; i++)
    {
        if (p(v[i], x))
        {
            vswap(v, boundary, i);
            boundary++;
        }
    }
    return boundary;
}

template<class X, class Predicate>
void mysort(std::vector<X> & v, Predicate p, size_t left, size_t right)
{
    //std::cout << "mysort: " << v << " " << left << " " << right << std::endl;
    if ((right - left) > 1)
    {
        size_t boundary = partition(v, p, left, right);
        //std::cout << "boundary = " << boundary << std::endl;
        mysort(v, p, left, boundary);
        mysort(v, p, boundary == left ? boundary + 1 : boundary, right);
    }
}

class Motorbike
{
    size_t m_id;
    int32_t m_finalPrice;
public:
    Motorbike()
        : m_id(0)
        , m_finalPrice(0)
    {}
    Motorbike(size_t id, int32_t finalPrice)
        : m_id(id)
        , m_finalPrice(finalPrice)
    {}
    void Id(size_t id)
    {
        m_id = id;
    }
    size_t Id() const
    {
        return m_id;
    }
    void Price(int32_t price)
    {
        m_finalPrice = price;
    }
    int32_t Price() const
    {
        return m_finalPrice;
    }
};

std::ostream& operator<< (std::ostream& stm, const Motorbike& bike)
{
    stm << "(" << bike.Id() << ", " << bike.Price() << ")";
    return stm;
}



std::vector<Motorbike> randomBikes(size_t count, int32_t lowPrice = 100, int32_t highPrice = 1000)
{
    std::vector<Motorbike> result;
    result.resize(count);
    for (size_t i = 0; i < count; i++)
    {
        result[i].Id(i);
        result[i].Price(lowPrice + rand() * (highPrice - lowPrice) / RAND_MAX);
    }
    return result;
}
std::vector<Motorbike*> bikePointers(std::vector<Motorbike> & bikes)
{
    std::vector<Motorbike*> result;
    result.resize(bikes.size());
    for (size_t i = 0; i < bikes.size(); i++)
    {
        result[i] = &bikes[i];
    }
    return result;
}

int main()
{
    //_CrtSetDbgFlag(_CRTDBG_CHECK_ALWAYS_DF);
    //_CrtDumpMemoryLeaks();
    //{
        //{
        //  std::vector<int32_t> data = { 3, 5, 1, 4, 2, 0 };
        //  std::cout << "original: " << data << std::endl;
        //  mysort(data, [](int32_t a, int32_t b) -> bool {return a < b;}, 0, data.size());
        //  std::cout << "sorted?   " << data << std::endl;
        //}
        //std::cout << "--------------------------------------------------------" << std::endl;
        //{
        //  std::vector<int32_t> data = { 3, 6, 1, 4, 2, 0, 5 };
        //  std::cout << "original: " << data << std::endl;
        //  mysort(data, [](int32_t a, int32_t b) -> bool {return a < b;}, 0, data.size());
        //  std::cout << "sorted?   " << data << std::endl;
        //}

        for(size_t run = 0; run < 10; run++)
        {
            auto bikes = randomBikes(5+run%2);
            auto bikes_p = bikePointers(bikes);
            std::cout << "original: " << bikes_p << std::endl;
            mysort(bikes_p, [](const Motorbike* m1, const Motorbike* m2)-> bool { return m1->Price() < m2->Price(); }, 0, bikes_p.size());
            std::cout << "sorted?   " << bikes_p << std::endl;
            std::cout << "--------------------------------------------------------" << std::endl;
        }
    //}

    //_CrtDumpMemoryLeaks();
    return 0;
}

应用于对象指针向量的快速排序 - 无限循环

Quick Sort applied to a vector of pointers to objects - infinite loop

c++