Сравнение сортировок обменами

[hdfan2]

За такую реализацию быстрой сортировки нужно руки отрывать по самые ягодицы. Передайте и не позорьтесь. Уберите постоянное создание списков и сделайте нормальный выбор пивота.

[valemak]

Скорее всего, Вы правы и вариант далёк от совершенства с практической точки зрения.

Честно говоря, я избегаю писать свои версии всех этих многочисленных сортировок, предпочитаю на просторах Интернета находить работающие версии, написанные, по всей видимости, куда большими специалистами чем я. Конечный выбор той или иной реализации обуславливается синтаксисом, наиболее иллюстрирующим основную суть алгоритма. Остальное, ИМХО, вторично в данной ситуации.

А вообще мне очень нравится вот эта версия:

def quick_haskell(data):
    return (quick_haskell([y for y in data[1:] if y <  data[0]]) + 
            data[:1] + 
            quick_haskell([y for y in data[1:] if y >= data[0]])) if len(data) > 1 else data

Но она не вписывается в стиль статьи в духе «о сортировках максимально доступными словами».

[Deosis]

Только у вас "быстрая" сортировка вместо обменов копирует данные в разные массивы, рекурсивно обрабатывает их и соединяет обратно.
Именно поэтому не хватило памяти.

[Pochemuk]

Почему-то ни в приквеле, ни в этой статье не рассматривается сортировка Шелла.

[valemak]

Сортировка Шелла принадлежит к классу сортировок вставками, к изучению которого приступаем в следующей статье.

[FireWind]

Простите за вопрос, зачем нужные все эти кастомные реализации сортировок, если в языках уже есть стандартные? А если нет — есть куча готовых библиотек?

[valemak]

Очень дельный вопрос.

Скажем так — данная серия статей ориентирована на тех, кто интересуется теорией алгоритмов.

[sibirier]

почему были выбраны такие медленные ЯП? и оба интерпретируемые
что скажете насчет тестов с LuaJIT, JVM, LLVM и .NET?
и что с компилируемыми ЯП?

думаю, если потестировать такие сортировки на JIT и с компилируемыми языками, то результаты будут более репрезентативные и весьма интереснее

[valemak]

Отличная идея.

Чтобы воплотить её в жизнь, осталось мне только в достаточной мере освоить какой-нибудь компилируемый язык программирования.

[enclis]

Для начала можно попробовать использовать PyPy вместо CPython.

[valemak]

А вот это уже ближе к моим реалиям. Статьи про сортировки вставками также через несколько недель будут завершаться финальным всеобщим тестированием, надо будет действительно это сделать на PyPy. Спасибо, что дали наводку.

[VaalKIA]

Прошлая статья понравилась и всегда из любопытства поглядываю на сравнения даже хорошо известных вещей. Зашёл и увидел треш и угар: хоть картинки и выглядят подобранными, но когда доходишь до таблиц, половина из них нифига не понятна, какие-то клоуны, пираты, машинки и биты, мотать на легенду нет никакого желания. Про секунды на урезанном мобильном проце, который может дать провалы на ровном месте, да ещё и в PHP и питоне, на взятых от балды реализациях… вы серьёзно? Почему нельзя измерить скорость в количестве сравнений/обменов, ведь это основной показатель?

[valemak]

Я поразмышляю над Вашими замечаниями и постараюсь в будущих статьях, где будут сравниваться другие классы сортировок, учесть критику.

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

Возможно, раз тестирование у меня такое корявое, я вообще откажусь от этого формата и статьи все будут сугубо теоретическими. В общем, чуть позже определюсь с этим.

[VaalKIA]

Кому интересны алгоритмы, если нет сравнений, показывающих в чём их сила? Ведь смысл статей о сортировках, а не конкретно о QuickSort, в том, что бы показать, что не всё так однозначно. А ещё можно и придумать очень наглядные представления:

Видео по сортировкам