Переполнение стека в quicksort

Question

Перед тем, как начать, я просто хочу сказать, что последние два часа я прочитал прочтение SO post о «Quicksort» и «переполнение стека», поэтому я не просто спрашиваю случайно, я буквально не знаю, что делать дальше ...

Хорошо, мне нужно реализовать быстрый алгоритм сортировки и по какой-то причине я не смог найти, я продолжаю получать ошибки переполнения стека. Я использую VS2010, поэтому я отлаживал его от начала до конца.

Итак, вот мой код:

const int THRESHOLD = 1; 

std::vector<int> data = *new std::vector<int>(); 

void GetPivotPoint(bool first, int leftBound, int rightBound, int& pivotID) 
{ 
    if(first) // We are choosing the first element as a pivot 
    { 
     pivotID = 0; 
     return; 
    } 
    else // We are choosing the median between 1, n/2 and n for our pivot 
    { 
     int left = leftBound; 
     int right = rightBound; 
     int center = (left + right)/2; 

     if(data[center] - data[left] < 0) data_manip::Swap(data, left, center); 
     if(data[right] - data[left] < 0) data_manip::Swap(data, left, right); 
     if(data[right] - data[center] < 0) data_manip::Swap(data, center, right); 

     data_manip::Swap(data, center, right); 
     pivotID = right; 
    } 
} 

int Partition(int left, int right) 
{ 
    int pivotID = 0; 
    GetPivotPoint(true, left, right, pivotID); 
    int pivot = data[pivotID]; 

    int i = left - 1; 
    int j = right + 1; 

    while(i < j) 
    { 
     i++; 
     while(data[i] < pivot) i++; 
     j--; 
     while(data[j] > pivot) j--; 

     if(i < j) 
     { 
      data_manip::Swap(data, i, j); 
     } 
    } 

    return j; 
} 

void Quicksort(int left, int right) 
{ 
    if(left + THRESHOLD > right) 
    { 
     algo::Bubblesort(data, left, right); 
    } 
    else 
    { 
     int partitionPoint = Partition(left, right); 

     Quicksort(left, partitionPoint); 
     Quicksort(partitionPoint + 1, right); 
    } 
} 

и вот реализация метода

inline void Swap(std::vector<int>& data, int p1, int p2) 
    { 
     int temp = data[p1]; 
     data[p1] = data[p2]; 
     data[p2] = temp; 
    } 

Своп() Я использую набор с более 1k и в них до 500K. Кроме того, в этом конкретном коде я использую параметр, чтобы получить первый элемент в качестве точки опоры, теперь я знаю, что это не оптимально, но мне нужно также проверить этот параметр. Если я использую медианную из трех вместо первого элемента, то я не получаю переполнение стека, однако, что может быть причиной этого, когда я использую первый элемент как ось вращения.

Баки для помощи

Answer 1

Вы получаете переполнение стека из следующей строки. Это тонкий, но очень важный. Вы должны добавить нижнее смещение к среднему значению, которое вы вычисляете.

int center = (left + right)/2; 

Попробуйте вместо этого:

int center = left + (right - left)/2; 

//////////////////////////////// ////////////////////////////////////////////////// /////////

Кроме того, у меня есть простая и элегантная реализация. Он замаскирован так, что он будет работать с любым типом данных. Это решение использует семантику перемещения C++ 11 и хороший дизайн API.

Вы можете оптимизировать его путем выполнения вставки Сортировки или Bubble Сортировки если размер массива меньше, чем, может быть, 7 предметов, является хорошей идеей, так как сам по себе QuickSort слишком много накладных расходов для малого массива размером

#include <vector> 
#include <memory> 

template <typename Item> 
bool less(Item v, Item w) 
{ 
    // Below line is written assuming that you data implements compareTo method 
    // You can also replace it with simple v < w 
    return v.compareTo(w) < 0; 
} 

template <typename Item> 
void exch(std::vector<std::shared_ptr<Item>> &arr, int i, int j) 
{ 
    if (i == j) return; 

    arr[i].swap(arr[j]); 
} 

template <typename Item> 
class QuickSort 
{ 
public: 
    static void sort(std::vector<std::shared_ptr<Item>> &arr) 
    { 
     sort(arr, 0, arr.size() - 1); 
    } 

private: 
    static void sort(std::vector<std::shared_ptr<Item>> &arr, int lo, int hi) 
    { 
     if (hi <= lo) return; 
     int j = partition(arr, lo, hi); 
     sort(arr, lo, j - 1); 
     sort(arr, j + 1, hi); 
    } 

    static int partition(std::vector<std::shared_ptr<Item>> &arr, int lo, int hi) 
    { 
     int i = lo, j = hi + 1; 

     while (true) 
     { 
      // Find item on left to swap 
      while (less((*arr[++i]), (*arr[lo]))) 
       if (i == hi) break; 

      // Find item on right to swap 
      while (less((*arr[lo].get()), (*arr[--j].get()))) 
       if (j == lo) break; 

      // Check if pointers swap 
      if (i >= j) break; 

      // Swap 
      exch(arr, i, j); 
     } 

     // Swap with partitioning item 
     exch(arr, lo, j); 

     return j; 
    } 
};