#algorithm #sorting
#алгоритм #сортировка
Вопрос:
Сортировка в оболочке или транспонирование нечетное-четное?
В моих тестах сортировка по четно-нечетному перемещению выполняется быстрее, верно?
Комментарии:
1. Уже существует множество сравнений алгоритмов сортировки, например, вы можете найти один здесь: home.westman.wave.ca /~rhenry/сортировать
2. Для чего? Насколько нам известно, подсчет сортировки может быть лучшим решением здесь .. дополнительная информация о том, что вы сортируете, помогла бы.
3. -1 за неясный вопрос. Что вы пытаетесь узнать, публикуя этот вопрос? Как отмечали другие комментаторы, сравнения алгоритмов сортировки широко доступны. Если бы ваш вопрос был чем-то вроде следующего, у вас было бы больше шансов на успех: «Я экспериментировал с сортировкой оболочки и сортировкой по четным и нечетным данным для данных типа XXX в структуре данных YYY. Я ожидал, что результатом будет AAA, но вместо этого получилось BBB. Я исключил возможность того, что это может быть из-за CCC или DDD. Как это можно объяснить?
Ответ №1:
Это зависит от вашего расположения данных.
Но QuickSort это довольно универсальный алгоритм сортировки, если то, что вы собираетесь сортировать, невелико. Если вы планируете сортировать огромные объемы данных, то вам нужно что-то с промежуточной памятью, например MergeSort .
Ответ №2:
Если я правильно помню, четно-нечетная сортировка очень похожа на пузырьковую сортировку, но ее можно выполнять параллельно.
На одном ядре процессора сортировка оболочкой, как правило, лучше, но пузырьковый / четный может выиграть на небольших наборах данных.
Ответ №3:
В большинстве случаев не имеет смысла кодировать свой собственный алгоритм сортировки. Почти в каждой среде есть встроенная сортировка, которая должна быть вашим первым выбором. Четно-нечетная транспозиция равна O (n ^ 2) для худших данных (на одном ядре).
Ответ №4:
Сортировка оболочки выполняется быстрее для больших массивов. Какой размер вам нужно взять массива, прежде чем вы увидите, что зависит от вашей реализации обоих алгоритмов.
Ответ №5:
В большинстве нетривиальных случаев действительно имеет смысл закодировать свой собственный алгоритм сортировки, но не все случаи нетривиальны. Все зависит от того, что вы знаете о сортируемых данных. Есть даже случаи, когда bubblesort является правильным выбором (или, возможно, даже оптимальным).
Комментарии:
1. Я уважаю вашу противоположную точку зрения. Его довольно легко закодировать
mylist.sort()на C с помощью STL. И к тому же эффективен.
Ответ №6:
Сортировка оболочки может быть реализована со многими вариантами начального размера промежутка и его уменьшения на каждом шаге. Оригинальный алгоритм является O(n^{3/2}) , но некоторые улучшения были представлены Хилбердом, Седжвиком и Чиурой. Итак, если вы спрашиваете, какой из них лучше, вы всегда должны указывать, какую реализацию вы используете. Таким образом, сортировка с использованием одной базовой оболочки должна выигрывать в каждом достаточно большом наборе данных. На нескольких ядрах, вероятно, выиграет четно-нечетная сортировка, потому что она может использовать больше процессорных блоков.