オブジェクトへのポインタのベクトルにクイックソートが適用されました - 無限ループ

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