Допустим, придумал улучшенную реализацию пузырьковой сортировки.
Где меряются алгоритмами, чтобы можно было сравнить свой вариант с другими программистами, так сказать в одной наглядной среде с одинаковыми условиями?
Ну алгоритмическая сложность конечно стала проще, но осталась квадратичной, это же вариант именно пузырьковой сортировки.
Сравнение классической реализации пузырька и моей, отличается примерно в 2-3 раза по скорости, а на почти отсортированных массивах (где нужно досортировать скажем 5-10 значений на миллион), моя показывает даже быстрее чем quicksort.
На хабру пока стремно. Там злые люди, минусуют налево и направо. Допилю код до чего-нить полезного, может тогда..
@saboteur_kievr Если О() осталась квадратичной, то меньше не стала(кажется) Пузырьковая сортировка вроде вообще простая, там и оптимизировать нечего. Все новомодные сортировки которые я видел по сути комбинации большой пятерки. Правда, выложите на любом авторитетном ресурсе, заинтриговали. И копирайт ведь получите.
Ну вот, вы уже описали случаи когда ваша сортировка особенно эффективна. Осталось только реально посчитать алгоритмическую сложность вашего алгоритма для подобных случаев (когда не отсортировано 10% выборки, при разных вероятностных распределениях и т.д.)
из этого можно очень крутую статью родить которая мало того что расскажет о нюансах выбора алгоритмов, придумывания своего под конкретную ситуацию и т.д. А еще эту статью можно кидать в качестве ответа на вопрос "зачем нас учат пузырек писать, это ж никогда не пригодится". Мол задача может попасться где модифицированный пузырек справляется эффективнее модных квиксортов.
