Пользователь
0,1
рейтинг
5 декабря 2013 в 19:14

Разработка → Глупая сортировка и некоторые другие, поумнее


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

Сегодня мы снова возьмём за основу stupid sort и внесём в неё другое маленькое, но существенное изменение. В результате получим совершенного другой эволюционный ряд сортировочных алгоритмов.

image: эволюция



Глупая сортировка




Кому лень смотреть первую серию, напомню, что из себя представляет глупая сортировка. Обходим по порядку массив и, встретив два неотсортированных соседа, меняем их местами. Затем возвращаемся на старт и «наша песня хороша, начинай сначала». Если в этой сортировке вместо возвращения просто идти дальше, то в получаем «пузырёк», который, как оказалось, тоже можно совершенствовать до бесконечности O(n log n).

Теперь поступим иначе. Обменяв два элемента, мы изменили порядок в массиве, и нужно как-то выяснить не вступает ли новое расположение в диссонанс с теми элементами, которые мы проверили ранее. Не будем прыгать в начало массива, не станем идти вперёд, а сделаем шаг назад. Если там теперь тоже не отсортировано, то установим строгую очерёдность по старшинству и сделаем ещё шаг назад. И так будем отступать до тех пор, пока не достигнем отсортированной части массива. После этого снова можно двигаться дальше.



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


Гномья сортировка


image: голландский садовый гном

Хотя гномам этот способ известен уже много столетий, человеческая раса о нём узнала совсем недавно. Уже 55 лет как человечество использовало сортировку слиянием, прошло 40 лет как стала известна быстрая сортировка, уже спустя 35 лет как разработана пирамидальная сортировка – и вот, только в 2000 году, этот бесхитростный, практически детский приём, был исследован Диком Груном:

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.


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



Так немного быстрее, хотя принципиально это временную сложность не улучшает, она как была так и остаётся O(n2). Но зато это приводит нас не только к новому способу сортировки, а даже к целому новому классу сортировок. И имя этой группе алгоритмов – «Сортировки вставками».

Сортировка простыми вставками


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

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



Тот же оптимизированный «гномик», но только для обмена используется буфер.

Временная сложность у этой сортировки O(n2), но не это главное. Сортировка вставками, судя по всему — наиболее эффективный вариант для почти отсортированных массивов. Этот факт используется в некоторых сложных алгоритмах сортировки. Помнится, я уже когда-то рассказывал про FlashSort, там при помощи вероятностного распределения быстро создаётся почти отсортированный массив, который затем доупорядочивается сортировкой вставками. Сортировка вставками используется в финальной части JSort, где путём построения неполной кучи массив оперативно почти сортируется. Timsort начинает сортировку массива с нахождения в нём почти упорядоченных отрезков, они также сортируются вставочным методом, а затем объединяются модифицированной сортировкой слиянием.

Как изволите видеть, хотя сортировка вставками сама по себе работает медленно, её сфера применения очень широка.

Ну, раз столь много букв написано про insertion sort, то рассказ будет не полным, если не сказать пару добрых слов про алгоритм, который называется…

Сортировка Шелла


Про сортировку Шелла уже есть статья на Хабре, поэтому буду очень краток.

Позавчера уже писал как из очень медленного «пузырька» можно сделать очень быструю «расчёску». Для этого сначала нужно сравнивать не соседей, а элементы, между которыми достаточно внушительное расстояние. Это позволяет на начальном этапе маленькие значения закинуть поближе к началу массива, большие – поближе к концу. Затем уменьшая разрыв, уже наводить в массиве локальные порядки.

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



Временная сложность у «шелла» – достаточно сложный вопрос. Дело в том, что до сих пор нет строгой формулы, по которой строится оптимальный числовой ряд изменяющихся расстояний между элементами в подгруппах. Последовательность строится эмпирически, на основании многочисленных тестов с различными входными данными и последнее наилучшее уточнение для вышеупомянутых «дельт» было определено в 2001 году:

1, 4, 10, 23, 57, 132, 301, 701.

Сортировку Шелла придумал, как ни странно, Дональд Шелл в 1959 году. В 2014-м автору, кстати, исполняется 90 лет, живёт и здравствует до сих пор, недавно в третий раз женился. Так что, изобретайте алгоритмы, держите мозги в тонусе – и переживёте 3-х жён полноценная многолетняя творческая деятельность Вам обеспечена.

Ссылки


Алгоритмы сортировко в Википедии
Sorting Algorithm on Wikipedia
Пузырьковая сортировка и все-все-все
И снова про сортировки: выбираем лучший алгоритм
Реализации сортировок на Розетте
Валерий Макаров @valemak
карма
60,2
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (22)

  • +9
    • 0
      Прикольное видео, но от него быстро как-то устаёшь. Просмотреть его полностью может только человек с очень крепкими нервами, да и то, если выключить звук.

      Кроме того, наглядно, но не понятно. Что происходит, ясно только тем, кто назубок знает эти алгоритмы. Разобраться «с нуля» по этому ролику, удавалось, наверное, немногим.
      • +7
        Раньше спокойно смотрел его. По большей части сортировок нахожу эти звуки приятными. Вот сейчас запустил, посмотрим как получится.
        • +2
          Возможно, Вы дискрет + тональный аудиал по репрезентативной системе.
          • +1
            а можете подробнее расшифровать что вы написали? А то про музыку всё что я знаю так это то что в начальной школе учитель музыки сказал что музыкальный слух у меня почти отсутствует и всё почти безнадёжно, но если очень захотеть то что-нибудь получится. Ну я не захотел.
            • 0
              http://ru.wikipedia.org/wiki/Репрезентативная_система

              Аудиалам особенно нравится воспринимать мир на слух.

              При этом различают дигитальных аудиалов — им нравится когда звуки облечены в осмысленный текст. Дигитальными аудиалами являются поэты-писатели, певцы, лингвисты, ведущие-дикторы теле- и радопрограмм, публичные политики и прочие представители профессий где приходится много говорить. Все «гаммар-наци» — дигитальные аудиалы.

              Что касается тональных аудиалов, то этим по душе не столько текст, сколько музыка, звуки природы, звуковые эффекты и пр. Тональными аудиалами являются композиторы, звукорежиссеры и просто любители хорошей музыки.

              Дискреты любят логику, классифицирование, абстрактное мышление, алгоритмы, мысленные эксперименты, точные науки. Они любят и умеют воспринимать мир чисто умозрительно. Это айтишники, математики-физики, шахматисты и т.д.

              Само собой, в человеке могут запросто доминировать две и более репрезентативные системы.
              Поскольку в этой анимации алгоритмов Вы особенно выделяете звуковое сопровождение, то и предположил что Вы — тональный аудиал. Ну и дискрет, само собой.
          • 0
            Да я дискрет, почитал что это такое. Причём очень сильно дискрет и прогрессирую.
      • +2
        Radix в начале неприятный, std первый который в середине где-то, gnome показался самым приятным, bitonic тоже ничего, bogo просто волшебен
        • +1
          «Музыка небесных сфер» для компьютерного гика )))
      • +1
        Когда-то во всех играх было примерно такое звуковое сопровождение.
      • +1
        Детали реализации по видео конечно непонятны, но примерное представление позволяет получить вполне. Я из всего только «heap sort» не понял. Кстати, последняя, «bogo» — это перемешивать случайным образом, до тех пор пока все элементы не выстроятся в идеальном порядке? Гениально! :)

        А звук прекрасный — ностальгия же!
    • +1
      Жаль последнюю сортировку до конца не показали)
  • 0
    А как же сортировка рандомом? Перемешали массив, проверили отсортирован или нет и т. д.
  • 0
    А какие методы используют браузеры в Javascript при .sort()?
  • +1
    В Java7 отказались от MergeSort в пользу алгоритма TimSort.
  • 0
    Пожалуй лучший цикл статей по сортировкам, которые приходилось читать (до сегодняшнего дня). Не знаю существует ли способ, но было бы хорошо иметь возможность запуска анимации сортировки по клику. Потомучто сейчас дочитываешь пункт и ждешь пока цикл завершится.
    • 0
      Спасибо за дельную идею. Пока гифки сделал просто кликабельными. Потом так же сделаю и для других статей.
      Хабр игнорирует к ссылкам параметр "_blank", имейте ввиду.

      К более-менее сложным сортировкам делаю анимацию на ютубе, но тут посчитал что для таких тривиальных алгоритмов это лишнее. Пожалуй, позже всё таки сконвертирую, просто в одном видео сразу по несколько штук будет, объединённых тематически.
  • 0
    и вот, только в 2000 году, этот бесхитростный, практически детский приём, был впервые описан Диком Груном

    Как??? Я упустил свой шанс! :) Именно гномью сортировку я придумал где-то в возрасте 12 лет, когда еще ничего о сортировках не знал. Много лет спустя узнал, что она называется гномья, и был уверен, что ее описанию сто лет в обед.
    • 0
      Сортировка, наверное, известна с незапамятных времён, просто ввиду её предельной простоты, на неё никто из учёных мужей не обращал внимания. Только в 2000 году некий Хармид Сабази-Азад сообщил на страницах научного издания о «новой сортировке» (ссылка на pdf). Первоначально предложил название stupid sort.

      Голландский учёный Дик Грун исследовал сортировку подробнее и предложил ей название, под которым она сейчас известна.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.