Daniel Daniel - 1 month ago 9
C++ Question

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

I cannot figure out why the algorithm results in an infinite loop. I am trying to sort the vector according to the final price. The pivot always stays the same. Maybe the problem is with the swapping of the objects

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

Often, algorithms from wikipedia, e.g. the quicksort algorithms are hard to transform into a working implementation because they fail to point out the assumed programming model implied by the given algorithm. For example, if it is a 0 based or a 1 based array and that they assume that the indices used are signed not unsigned integers.

Then, people start trying to use those algorithms, here, for example in C++ and run into all sorts of problems. Quite a waste of time... And from looking at the code given in the question, I assume the author of the question tried to use info from wikipedia...

Since this is obviously homework, impress your teacher and use the code below. Quicksort is tricky to get right and it can take quite a while to find out if you should write lo = left + 1 or lo = left etc.

#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;
}