Рубрика «сортировка»

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса «Алгоритмы и структуры данных» от OTUS. По ссылке вы сможете подробно узнать о курсе, а также бесплатно посмотреть запись Demo-урока по теме: «Три алгоритма поиска шаблона в тексте».


Введение

Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе «Алгоритмы и структуры данных» дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.
Читать полностью »

«Просто так» результат SQL-запроса возвращает записи в том порядке, который наиболее удобен серверу СУБД. Но человек гораздо лучше воспринимает хоть как-то упорядоченные данные — это помогает быстро сравнивать соответствие различных датасетов.

Поэтому со временем у разработчика может выработаться рефлекс «Дай-ка я на всякий случай это вот отсортирую!» Конечно, иногда подобная сортировка бывает оправдана прикладными задачами, но обычно такой случай выглядит как в старом анекдоте:

Программист ставит себе на тумбочку перед сном два стакана. Один с водой — на случай, если захочет ночью пить. А второй пустой — на случай, если не захочет.

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

PostgreSQL Antipatterns: убираем медленные и ненужные сортировки - 1

Читать полностью »

Вступление

Эта статья описывает стабильный нерекурсивный адаптивный алгоритм сортировки слиянием под названием quadsort.

Четверной обмен

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

    if (val[0] > val[1])
    {
        tmp[0] = val[0];
        val[0] = val[1];
        val[1] = tmp[0];
    }

В четверном обмене происходит сортировка с помощью четырёх подменных переменных (своп). На первом этапе четыре переменные частично сортируются в четыре своп-переменные, на втором этапе они полностью сортируются обратно в четыре исходные переменные.

Алгоритм сортировки quadsort - 1
Этот процесс показан на диаграмме выше.
Читать полностью »

Свежий взгляд на традиционные концепции. Сегодня будет такой «декарт» которого в школе не проходили.

Сортировка декартовым деревом - 1


Суть алгоритма в том, что на основании массива строится так называемое декартово дерево. А из построенного декартового дерева очень легко получить все элементы в порядке возрастания или убывания.Читать полностью »

Введение

Всё началось с короткого скрипта, который должен был объединить информацию об адресах e-mail сотрудников, полученных из списка пользователей почтовой рассылки, с должностями сотрудников, полученными из базы отдела кадров. Оба списка были экспортированы в текстовые файлы в кодировке Юникод UTF-8 и сохранены с юниксовскими концами строк.

Содержимое mail.txt

Иванов Андрей;ia@example.com

Содержимое buhg.txt

Иванова Алла;маляр
Ёлкина Элла;крановщица
Иванов Андрей;слесарь
Абаканов Михаил;маляр

Для объединения файлы были отсортированы юниксовской командой sort и поданы на вход юниксовской программе join, которая неожиданно завершилась с ошибкой:

$> sort buhg.txt > buhg.srt
$> sort mail.txt > mail.srt
$> join buhg.srt mail.srt > result
join: buhg.srt:4: is not sorted: Иванов Андрей;слесарь

Просмотр результата сортировки глазами показал, что в целом сортировка правильная, но в случае совпадений мужских и женских фамилий, женские идут перед мужскими:

$> sort buhg.txt
Абаканов Михаил;маляр
Ёлкина Элла;крановщица
Иванова Алла;маляр
Иванов Андрей;слесарь

Выглядит как глюк сортировки в Юникоде или как проявление феминизма в алгоритме сортировки. Первое, конечно, правдоподобнее.

Читать полностью »

Сортировка слабой кучей - 1


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

При сортировке с помощью слабой кучи всегда меньше количество сравнений и обменов, чем если использовать обычную кучу. Так что да, слабая куча сильнее, чем обычная куча.Читать полностью »

Всем давно известно, что на видеокартах можно не только в игрушки играть, но и выполнять вещи, никак не связанные с играми, например, нейронную сеть обучить, криптовалюту помайнить или же научные расчеты выполнить. Как так получилось, можно прочитать тут, а я хотел затронуть тему того, почему GPU может быть вообще интересен рядовому программисту (не связанному с GameDev), как подступиться к разработке на GPU, не тратя на это много времени, принять решение, нужно ли вообще в эту сторону смотреть, и «прикинуть на пальцах», какой профит можно получить. 

Вычисления на GPU – зачем, когда и как. Плюс немного тестов - 1

Читать полностью »

В продолжение темы хочу поделиться своим кодом, который обгоняет std::sort() из актуальных версий GNU C++ Library и (примерно, нет точных данных) повторяет результат "Сортировки Александреску" с CppCon 2019.

Читать полностью »

Как нетрудно догадаться, я знаю ответ на этот вопрос, но, поскольку моя статья с описанием алгоритма сортировки «воронкой» была здесь встречена, мягко говоря, нервозно, я решил провести-таки тестирование «по образу и подобию» тех, которые обычно проводятся — в основном, конечно, по материалам статей, представленных здесь же, на Хабре.

В Интернете не представлены трудные массивы для алгоритмов сортировки (мне, во всяком случае, их найти не удалось), а многочисленные «сравнительные анализы» алгоритмов на массивах в несколько сотен или тысяч элементов, просто смешны, а потому я решил прогнать «воронкой» те массивы, на которых проводились исследования с количеством элементов, по крайней мере, 10^5 и более.

Сначала небольшой обзор того, что пишут про алгоритмы сортировки с моими комментариями:
Читать полностью »

Сортировка «Ханойская башня» - 1

Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.) Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js