Быстрая сортировка / вектор / проблема раздела

Question

У меня проблема со следующим кодом:

class quicksort {
private:
  void _sort(double_it begin, double_it end)
  {
    if ( begin == end ) { return ; }
    double_it it = partition(begin, end, bind2nd(less<double>(), *begin)) ;
    iter_swap(begin, it-1);
    _sort(begin, it-1);
    _sort(it, end);
  }
public:
  quicksort  (){}
  void operator()(vector<double> & data)
  {
    double_it begin = data.begin();
    double_it end = data.end() ;
    _sort(begin, end);
  }
};

Однако это не будет работать для слишком большого количества элементов (работает с 10 000 элементов, но не с 100 000).

Пример кода:

int main()
{
  vector<double>v ;

  for(int i = n-1; i >= 0 ; --i)
    v.push_back(rand());  

  quicksort f;
  f(v);

  return 0;
}

Разве функция STL не работает для таких размеров? Или я что-то упустил?

Большое спасибо за вашу помощь.

Answer 1

Я вижу пару проблем. Я бы не включил пивот в ваше разбиение, поэтому я бы использовал эту строку вместо:

double_it it = partition(begin + 1, end, bind2nd(less<double>(), *begin)) ;

Кроме того, я бы не стал включать пивот в ваши будущие сортировки, поэтому я бы сделал

_sort(begin, it - 2);

вместо этого, но вы должны быть осторожны, чтобы it - 2 было не меньше begin, поэтому сначала проверьте it - 1 != begin. Нет необходимости постоянно сортировать ось - она ​​уже находится в правильном месте. Это просто добавит много лишней ненужной рекурсии.

Конечно, у вас все еще могут быть проблемы переполнения стека с этим кодом даже после изменений. Например, если вы отсортируете уже отсортированный массив с этим кодом, производительность будет O (N ^ 2), а если N очень большое, вы получите переполнение стека. Использование случайно выбранной сводной точки по существу устранит проблему для проблемы с отсортированным массивом, но у вас все еще могут быть проблемы, если массив все тот же элемент. В этом случае вам нужно изменить алгоритм, чтобы использовать разбиение Bentley-McIlroy или подобное. Или вы можете изменить его на интросорт и изменить на heapsort, когда глубина рекурсии становится очень большой.

Answer 2

Вы проверили, что для вашего doublt_it it не установлено значение begin? Это вызвало бы проблему в строке iter_swap(begin, it-1);.

Не так ли?

Хорошо, думаю, # 2 - переполнение стека, потому что вы слишком много рекурсии. Некоторые компиляторы не могут обрабатывать много рекурсивных циклов. 100 тыс. Могли бы сделать то же самое, в то время как 10 тыс. Могли справиться.

Answer 3

Проверьте следующий код. Я написал это быстро, без шаблонов и использования итераторов, но идея состоит в том, чтобы доказать, что быстрая сортировка в порядке сортировки огромных массивов (это довольно очевидно, хе-хе) .

Итак, что-то не так с вашей быстрой сортировкой с точки зрения алгоритма, а не с точки зрения переполнения стека / других вещей компилятора. Я имею в виду, что вы всегда должны пытаться понять, что является причиной и устранить «глубокую» проблему, но не «мелкую».

Обратите внимание, что мой код может быть легко переписан с использованием того же подхода итератора, который использовался в вашем коде (возможно, это потребует некоторых дополнительных проверок, но, в любом случае, его легко реализовать).

#include <vector>
#include <algorithm>
#include <utility>
#include <functional>

class sorter {
public:
   sorter(std::vector<int>& data) : data(data) { }

   void quicksort(int p, int r) {
      if (p < r) {
         int q = std::partition(data.begin() + p, data.begin() + r, std::bind2nd(std::less<int>(), data[r])) - data.begin();
         std::swap(data[q], data[r]);
         quicksort(p, q - 1);
         quicksort(q + 1, r);
      }
   }

   void sort() {
      quicksort(0, data.size() - 1);
   }

private:
   std::vector<int>& data;
};

int main() {
   size_t n = 1000000;
   std::vector<int> v;

   for(int i = n - 1; i >= 0 ; --i)
      v.push_back(rand());  

   sorter s(v);
   s.sort();

   return 0;
}

# EDIT

Материал итератора будет означать что-то вроде

class sorter {
public:
   typedef std::vector<int> data_type;
   sorter(std::vector<int>& data) : data(data) { }

   void quicksort(data_type::iterator p, data_type::iterator r) {
      data_type::iterator q = std::partition(p, r, std::bind2nd(std::less<int>(), *r));
      std::iter_swap(q, r);

      if (q != p)
         quicksort(p, q - 1);
      if (q != r)
         quicksort(q + 1, r);
   }

   void sort() {
      quicksort(data.begin(), data.end() - 1);
   }

private:
   std::vector<int>& data;
};