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

Самый простой (и неожиданный) алгоритм сортировки? - 1

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

1. Алгоритм

Большинству из нас хорошо известны такие простые алгоритмы сортировки, как сортировка пузырьком. По крайней мере, нам так кажется. Оказывались ли вы когда-нибудь в ситуации, когда вам нужно записать псевдокод сортировки пузырьком, и вы осознавали, что он не так прост, как кажется, и с первого раза правильно написать его не удаётся? Нужно внимательно следить за тем, чтобы индексы циклов начинались и заканчивались нужными значениями и не выходили за границы, а также правильно обрабатывать флаговые переменные. Разве не было бы здорово иметь простой алгоритм без всей этой возни? Ниже представлен такой алгоритм, сортирующий массив A из n элементов в неубывающем порядке. Для простоты доказательства массив начинается с 1, то есть имеет элементы A[1],..., A[n].

Алгоритм 1 ICan’tBelieveItCanSort(A[1..n]):

for i = 1 to n do
  for j = 1 to n do
    if A[i] < A[j] then
      swap A[i] and A[j]

Вот, собственно, и всё. Он просто обходит в цикле каждую пару значений (i, j) стандартным способом из двойного цикла for, выполняет сравнение и обмен значениями. Разве можно придумать что-то ещё более простое? Возможно первой реакцией увидевшего этот алгоритм будет что-то типа «это не может быть верно» или «знак неравенства направлен в другую сторону, да и индексы цикла указаны неверно». Но нет, он действительно правильно сортирует в возрастающем порядке.Читать полностью »

Прим. Wunder Fund: не спешите минусовать эту публикацию — её перевода на Хабре ещё не было :)

Это — продолжение моей предыдущей публикации (вот — перваявторая и третья части перевода), посвящённой тому, как я создал алгоритм сортировки, который быстрее std::sortЧитать полностью »

За 20 лет у меня скопилось несколько тысяч фотографий: праздники, свадьбы, рождение детей, и прочее, прочее... Понятно что снималось всё это на разные цифровики, присылалось почтой, сливалось через ICloud и GDrive, FTP, самба и т.п. По итогу всё это превратилось в дикий хаос папок и что-то найти в архиве можно было только с большим трудом.

В какой-то момент мне нечем было заняться это надоело и я за пару дней накидал скрипт, который всё это безумие раскидал по годам->месяцам->Читать полностью »

Прим. перев.: это не совсем обычный перевод, потому что в его основе не отдельно взятая статья, а недавний случай со Stack Exchange, ставший главным хитом ресурса в этом месяце. Его автор задает вопрос, ответ на который оказался настоящим откровением для некоторых посетителей сайта.

Сжимая каталоги по ~1,3 ГБ, в каждом из которых по 1440 файлов JSON, я обнаружил 15-кратную разницу между размером архивов, сжатых с помощью tar на macOS или Raspbian 10 (Buster), и архивов, полученных при использовании библиотеки tarfile, встроенной в Python.

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

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса «Алгоритмы и структуры данных» от 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


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

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


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