@valemak29 июн 2018 в 12:02

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

9 мин

7.8K

PHP * Python * Алгоритмы * Программирование * Тестирование IT-систем *

Комментарии 14

@hdfan2 29 июн 2018 в 14:53

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

@valemak 29 июн 2018 в 16:44

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

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

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

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 2 июл 2018 в 06:04

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

@Pochemuk 29 июн 2018 в 22:52

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

@valemak 30 июн 2018 в 04:36

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

@FireWind 30 июн 2018 в 14:49

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

@valemak 30 июн 2018 в 15:27

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

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

@sibirier 30 июн 2018 в 15:25

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

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

@valemak 30 июн 2018 в 15:33

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

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

@enclis 30 июн 2018 в 16:38

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

@valemak 30 июн 2018 в 17:11

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

@VaalKIA 1 июл 2018 в 06:40

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

@valemak 1 июл 2018 в 07:18

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

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

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

@VaalKIA 1 июл 2018 в 08:54

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

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий