быстрая сортировка в C ++ выполняется медленно

StackOverflow https://stackoverflow.com/questions/1208766

  •  05-07-2019
  •  | 
  •  

Вопрос

У меня есть 9 значений в виде матрицы, и мне нужно вычислить медиану по этим значениям как часть процесса моделирования.

Я использую быструю сортировку в C ++ (т.е. qsort()), что приводит к замедлению процесса (поскольку этот процесс повторяется несколько раз).

Есть ли лучший алгоритм сортировки, который я мог бы использовать?

Это было полезно?

Решение

Сортировка по медиане очень неэффективна. Вместо этого вы можете использовать STL nth_element: 

#include <algorithm>

// Assuming you keep the elements in a vector v of size len

std::nth_element( v.begin(), v.begin()+len/2, v.end() );
median = v[len/2];

 //... or, if the elements are in a simple array v[len], then

std::nth_element( v, v+len/2, v+len );
median = v[len/2];

Примечание: элемент nth_element изменит вектор / массив v. Сначала сделайте копию, если вам нужно сохранить оригинал.

Другие советы

Пожалуйста, пожалуйста, никогда не рекомендуйте пузырьковую сортировку, кроме мазохистов!

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

Редактировать: исправлено форматирование, подчеркивая предложенный ответ.

Всего 9 значений?Быстрая сортировка - это перебор.

Возможно, используйте сортировку по вставке, пузырьковую сортировку или другие более простые алгоритмы сортировки при работе с небольшими наборами данных.

Производительность

Пузырьковая сортировка имеет как наихудшую, так и среднюю сложность О(n2), где n - количество сортируемых элементов.Существует множество алгоритмов сортировки с существенно лучшей сложностью для наихудшего случая или средней сложности O (n log n).Даже другие алгоритмы сортировки О (n2), такие как сортировка по вставке, как правило, имеют лучшую производительность, чем сортировка пузырьками.Следовательно, пузырьковая сортировка не является практичным алгоритмом сортировки, когда n велико.

Однако, конечно, вам даже не нужно было сортировать, чтобы получить медиану, как предлагали другие.

<Ол>

  • Как уже упоминалось, нет необходимости полностью сортировать, чтобы получить медиану.

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

    • Использование быстрой сортировки только для 9 значений будет довольно неэффективным. Для такого небольшого размера выборки вам гораздо лучше использовать сортировку выбора или замену сортировки ... в этих методах сортировки очень мало затрат.

    Quicksort и Mergesort действительно светятся, когда размер выборки достигает порогового значения, возможно, 50+.

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

    Алгоритм std :: sort () почти всегда предпочтительнее qsort (). Обычно он проще в использовании и работает быстрее.

    Если вы хотите вникнуть в подробности, на самом деле есть семейство алгоритмов сортировки. Страуструп пишет на языке программирования C ++ , что std :: sort часто не совсем подходит для использования. В этом случае std :: nth_element (), вероятно, то, что вы хотите.

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

    С настройкой Quicksort связана стоимость, и когда у вас недостаточно значений, использовать этого зверя бесполезно.

    Вставка сортировки.

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

    Есть разные подходы. Вы можете использовать структуры данных, где вы сортируете при вставке, и есть места, где вы сортируете полный набор данных. Вам просто нужно найти оптимальный алгоритм.

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top