Где можно проверить свою реализацию сортировки?

Question

[Saboteur]

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

Answer 1

[Сергей Протько]

придумал улучшенную реализацию пузырьковой сортировки.

99% что вы придумали что-то уже существующее.

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

Comments

[Saboteur]

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

Сравнение классической реализации пузырька и моей, отличается примерно в 2-3 раза по скорости, а на почти отсортированных массивах (где нужно досортировать скажем 5-10 значений на миллион), моя показывает даже быстрее чем quicksort.

На хабру пока стремно. Там злые люди, минусуют налево и направо. Допилю код до чего-нить полезного, может тогда..

[uvelichitel]

@saboteur_kievr Если О() осталась квадратичной, то меньше не стала(кажется) Пузырьковая сортировка вроде вообще простая, там и оптимизировать нечего. Все новомодные сортировки которые я видел по сути комбинации большой пятерки. Правда, выложите на любом авторитетном ресурсе, заинтриговали. И копирайт ведь получите.

[Сергей Протько]

Сергей: я вам плюсик поставлю)

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

из этого можно очень крутую статью родить которая мало того что расскажет о нюансах выбора алгоритмов, придумывания своего под конкретную ситуацию и т.д. А еще эту статью можно кидать в качестве ответа на вопрос "зачем нас учат пузырек писать, это ж никогда не пригодится". Мол задача может попасться где модифицированный пузырек справляется эффективнее модных квиксортов.

[Saboteur]

Сергей Протько: Ок, постараюсь через несколько дней допилить в какой-то приличный вид и выложу на хабре )

[Андрей]

Я тоже поставлю )

[Saboteur]

Сергей Протько: habrahabr.ru/post/274493

Answer 2

[Don Kaban]

Допустим, придумал улучшенную реализацию пузырьковой сортировки.

Смешно.