Блог

Главная - Вопросы по программированию - Почему моя быстрая сортировка медленнее, чем сортировка слиянием?

Почему моя быстрая сортировка медленнее, чем сортировка слиянием?

#c #performance #sorting #merge

Вопрос:

Это моя реализация. Когда я помещаю 100 сотен массивов размером 1000000, это занимает 300 секунд. Мой другой алгоритм, сортировка слиянием, делает это в течение 40 секунд. Интересно, есть ли какие-то вещи, которые могли бы замедлить мой алгоритм.

 template <typename TYP> void quick_sort(TYP *tab, int poczatek, int koniec) {
  int i = poczatek;
  int j = poczatek;
  int srodek = (poczatek   koniec) / 2;
  int piwot = tab[srodek];

  swap(tab[srodek], tab[koniec]);

  for (i = poczatek; i < koniec; i  ) {
    if (tab[i] < piwot) {
      swap(tab[i], tab[j]);
      j  ;
    }
  }
  swap(tab[koniec], tab[j]);

  if (poczatek < j - 1)
    quick_sort(tab, poczatek, j - 1);

  if (j   1 < koniec)
    quick_sort(tab, j   1, koniec);
}

Комментарии:

1. Не могли бы вы также поделиться другим алгоритмом? И как вы измеряете код? В частности, какие материалы вы предоставляете?

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

3. Попробуйте запустить встроенный C qsort и посмотреть его время, чтобы понять, является ли алгоритм вырожденным случаем или ваша реализация нарушена.

4. В любом случае 40 секунд кажутся довольно медленными для массива из 1000000 значений. Каков тип ввода? Вы включили флаги оптимизации компилятора?

5. qsort не требует, чтобы он действительно использовал алгоритм быстрой сортировки.

Ответ №1:

Быстрая сортировка имеет среднее время выполнения O(n log(n)) , но наихудшую сложность, O(n^2) если ось выбрана неправильно. Что касается вашего входного массива, выбранный вами разворот может быть действительно плохим. Чтобы предотвратить это, вы можете реализовать Интросорт. Кроме того, вы можете использовать лучший метод для выбора разворота: например, правило медианы из трех.

Кроме того, быстрая сортировка выполняется медленно для небольших массивов. Вы можете значительно повысить его производительность, например, с помощью сортировки вставок для массивов размером менее 15. Последние рекурсивные вызовы будут выполняться быстрее, что приведет к общему ускорению выполнения.

Наконец, для быстрой сортировки используется схема разделения Lomuto, которая, вероятно, не самая эффективная. Вы можете попробовать использовать схему разделения Хоара.

Метки: ,