Какой алгоритм сортировки быстрее?

Question

Сортировка оболочки или нечетно-четное транспонирование?

В моих тестах приходит Четно-нечетное транспонирование быстрее, правильно?

Answer 1

Это зависит от вашего макета данных.

Но QuickSort - это довольно универсальный алгоритм сортировки, если то, что вы собираетесь сортировать, невелико.Если вы планируете сортировать огромные объемы данных, вам нужно что-то с промежуточной памятью, например MergeSort.

Answer 2

В большинстве случаев не имеет смысла кодировать собственный алгоритм сортировки.Почти в каждой среде есть встроенная сортировка, которая должна быть вашим первым выбором.Четно-нечетное преобразование равно O (n ^ 2) для худших данных (на одном ядре).

Answer 3

Если я правильно помню, сортировка по нечетно-четному принципу очень похожа на сортировку по пузырькам, но она может выполняться параллельно.

На одном ядре ЦП сортировка в целом лучше, но пузырьковая / нечетная четность может выиграть для небольших наборов данных.

Answer 4

Сортировка оболочки может быть реализована с множеством вариантов начального размера зазора и его уменьшения на каждом шаге. Оригинальный алгоритм - O(n^{3/2}), но некоторые улучшения были представлены Хилбердом, Седжвиком и Чиурой. Поэтому, если вы спрашиваете, что лучше, вы всегда должны сказать, какую реализацию вы используете. Таким образом, в каждом достаточно большом наборе данных должна быть реализована единая сортировка ядра. На нескольких ядрах, вероятно, победит нечетно-четная сортировка, потому что она может использовать больше процессорных единиц.

Answer 5

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

Answer 6

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