И это не пузырьковая, а нечто гораздо более тупое.
Как-то после обеда, стоя в коридоре с чашечкой кофе, мне пришла в голову мысль. Что ведь для того, чтобы убедиться, что массив отсортирован, надо сделать всего n-1 сравнение. Например, для массива длины 4 таких сравнения будет 3:
if (a0 < a1 < a2 < a3) А получив утвердительный ответ на этот вопрос, мы можем сразу вернуть готовый массив:
if (a0 < a1 && a1 < a2 && a2 < a3) return [a0, a1, a2, a3];
Многие программисты думают, что Quick Sort — самый быстрый алгоритм из всех существующих. Отчасти это так. Но работает она действительно хорошо только если правильно выбран опорный элемент (тогда сложность составляет O (n log n)). В противном же случае асимптотика будет примерно такой же как и в пузырика (то-есть O (n2)).
При этом, если массив уже отсортирован, то алгоритм всё-равно будет работать не быстрее, чем за O (n log n)
Исходя из этого, я решил написать свой алгоритм для сортировки массива, который работал бы лучше за quick_sort. И если массив уже отсортирован, то не прогонять его кучу раз, как это бывает у многих алгоритмов.
«Дело было вечером, делать было нечего», — Сергей Михалков.
А теперь давайте обо всём по порядку
Чтобы наш алгоритм всегда работал быстро, нужно чтобы в среднем случае асимптотика была хотя бы O (n log n), а в лучшем — O (n). Все мы прекрасно знаем, что в лучшем случае сортировка вставками работает за один проход. Но в худшем ей придётся гонять по массиву столько раз, сколько в нём элементов.
Прим. перев.: Это перевод истории о том, как нелегко оказалось написать параллельную быструю сортировку (quicksort) на Хаскеле. Оригинал статьи написан в 2010 году, но, мне кажется, он до сих пор поучительный и во многом актуальный.
Есть много примеров того, как Хаскель делает простые проблемы сложными. Вероятно, самый известный из них—это решето Эратосфена, которое легко написать на любом императивном языке, но настолько сложно написать на Хаскеле, что почти все решения, которые преподавались в университетах и использовались в исследованиях последние 18 лет, оказались неправильными. На их несостоятельность обратила внимание Мелисса О'Нил [Melissa O'Neill] в своей важной научной работе "Настоящее решето Эратосфена". В ней приводится прекрасное описание того, что не так в старых подходах, и как их надо исправить. Решением Мелиссы было использовать очередь с приоритетом [priority queue] для реализации решета. Правильное решение оказалось в 10 раз длиннее, чем намного более простое решение на F# и в целых 100 раз длиннее, чем оригинальный изуродованный алгоритм на Хаскеле.
Читать полностью »
Ранее я уже публиковал статью о Однострочниках на С++, теперь я хочу рассказать несколько STL алгоритмов и не только.
Заинтересовавших прошу под кат.
Читать полностью »
Лично я, при всей моей вере в C++, считаю, что даже в редакции 2011, этот язык крайне недружелюбен в плане многозадачности и многопоточности. В качестве очередной попытки переубедить себя в этом я попробовал сделать многопоточный QuickSort.
В этом алгоритме получается после фазы разбиения запустить сортировки подчастей параллельно.
Вот мой наивный велосипед:
Читать полностью »