Сортировки слиянием


    Сортировки слиянием работают по такому принципу:

    1. Ищутся (как вариант — формируются) упорядоченные подмассивы.
    2. Упорядоченные подмассивы соединяются в общий упорядоченный подмассив.

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



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

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


    Автором данной концепции является Джон фон Нейман. Иногда встречается спорное утверждение, что сортировку он придумал во время работы над Манхеттенским проектом, поскольку перед ним стояла задача обеспечить эффективные расчёты огромного количества статистических данных при разработке ядерной бомбы. Сложно оценить правдоподобность данной версии, поскольку первые его работы по сортировке слиянием датируются 1948 годом, а создание бомбы были завершено 3-мя годами раннее. Впрочем, что же там за атомная сортировка, давайте на неё взглянем.

    Естественное неймановское слияние



    На неймановский алгоритм повлияли конструктивные особенности компьютеров 40-х годов. Выглядело это так:

    1. Всего используется три магнитные ленты — основная, на которой записаны неотсортированные данные и две вспомогательные.
    2. Данные последовательно считываются с основной ленты.
    3. Пока последовательно считываемые данные представляют из себя упорядоченный подмассив, они переписываются на одну из вспомогательных лент.
    4. Как только завершается очередной отсортированный подмассив (т.е. на основной ленте встречается элемент, меньший чем предыдущий), на вспомогательной ленте ставится указатель (конец подмассива) и происходит переключение на другую вспомогательную ленту.
    5. Пункты 2-4 повторяются снова, только данные переносятся уже на другую вспомогательную ленту. При завершении очередного упорядоченного подмассива на основной ленте происходит поочерёдное переключение то на одну вспомогательную ленту, то на другую.
    6. Когда все данные с основной ленты считаны, происходит обработка вспомогательных лент.
    7. С обеих вспомогательных лент поочерёдно считываются данные.
    8. При этом очередные данные с двух лент сравниваются между собой. По результатами сравнения на основную ленту записывается меньший элемент из пары.
    9. Так как границы массивов на вспомогательных лентах отмечены указателями, считывание и сравнение происходит только в пределах отсортированных подмассивов.
    10. Если на одной из вспомогательных лент закончились элементы очередного подмассива, то с оставшейся ленты остаток подмассива просто переносится на основную ленту.
    11. Повторяем весь процесс заново до тех пор, пока данные на основной ленте не будут собой представлять полностью упорядоченный массив.

    Неймановская сортировка является адаптивным алгоритмом: она не просто фиксирует отсортированные куски массива, но и в первую очередь старается увеличить их, чтобы затем на основе удлинённых упорядоченных подмассивов формировать ещё более длинные упорядоченные подмассивы. Поэтому её ещё называют адаптивной сортировкой слиянием.

    Сложность данного алгоритма скромна — O(n2), и, тем не менее, для пионеров ламповых вычислений это был прорыв.

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

    Прямое слияние Боуза-Нельсона


    Строго говоря, алгоритм Боуза-Нельсона — это сортировочная сеть, а не сортировка. В процессе массив и все его подмассивы делятся пополам и ничто не препятствует тому, чтобы все эти половинки на всех этапах обрабатывались параллельно. Однако можно представить и в виде именно сортировки. А до темы сортировочных сетей мы когда-нибудь доберёмся тоже.



    1. Массив делится пополам — на левую и правую половины.
    2. Элементы разбиваются на группы.
    3. На первой итерации это двойки элементов (1-й элемент левой половины + 1-й элемент правой половины, 2-й элемент левой половины + 2-й элемент правой половины и т.д.), на второй итерации — четвёрки элементов (1-й и 2-й элементы левой половины + 1-й и 2-й элементы правой половины, 3-й и 4-й элементы левой половины + 3-й и 4-й элементы правой половины и т.д.), на третьей — восьмёрки и т.д.
    4. Элементы каждой группы из левой половины являются отсортированным подмассивом, элементы каждой группы из правой половины также являются отсортированным подмассивом.
    5. Производим слияние отсортированных подмассивов из предыдущего пункта.
    6. Возвращаемся в пункт 1. Цикл продолжается до тех пор, пока размеры групп меньше размера массива.

    Может показаться, что и тут требуется дополнительная память. Но нет! Для более понятного восприятия в анимации левая и правая половины массива расположены друг на другом, чтобы очевиднее было взаимное расположение сравниваемых подмассивов. Однако ввиду строгого деления пополам возможен алгоритм, при котором все сравнения и обмены делаются на месте, без привлечения дополнительных ресурсов по памяти. Что весьма нестандартно для сортировки слиянием.

    def bose_nelson(data):
        m = 1
        while m < len(data):
            j = 0
            while j + m < len(data):
                bose_nelson_merge(j, m, m)
                j = j + m + m
            m = m + m
        return data
    
    def bose_nelson_merge(j, r, m):
        if j + r < len(data):
            if m == 1:
                if data[j] > data[j + r]:
                    data[j], data[j + r] = data[j + r], data[j]
            else:
                m = m // 2
                bose_nelson_merge(j, r, m)
                if j + r + m < len(data):
                    bose_nelson_merge(j + m, r, m)
                bose_nelson_merge(j + m, r - m, m)
        return data

    Таки есть во всех сортировках слиянием нечто, что роднит их с водородной бомбой. Сначала происходит деление, потом синтез.

    Ссылки


    Merge / Слияние

    Статьи серии:



    Обе упомянутые в сегодняшней статье сортировки теперь доступны в приложении AlgoLab (кто изучает алгоритмы с помощью этого Excel-приложения — обновите файл). А всего через пару дней, с выходом скорого продолжения о сортировках слияния, будут доступны ещё несколько алгоритмов этого класса.

    Для сортировки Боуза-Нельсона поставлено ограничение — размер массива должен быть степенью двойки. Если это условие не будет выполнено, то макрос обрежет массив до подходящего размера.
    EDISON Software - web-development
    Статья написана при поддержке компании EDISON Software, которая пишет софт 3d-реконструкции и занимается разработкой сложного измерительного оборудования.

    Edison

    304,00

    Изобретаем успех: софт и стартапы

    Поделиться публикацией

    Похожие публикации

    Комментарии 10
      +3

      Сортировка слиянием. Как много напомнил этот заголовок. В далеком 1976 году я начинал службу в Прибалтике в г. Вентспилс . Из вычислительной техники у нас была ЭВМ М-220. А это 4К ОЗУ, 28К магнитный барабан и штук восемь лентопротяжек. Информации обрабатывалась немерино. Машинисток было много и они трудились без отдыха. И я только что закончивший Академию Ф.Э. Дзержинского, решил автоматизировать процесс формирования отчетов. За прототив был взят генератор отчетов от IBM — RPG. Так родился отечественный генератор (чем не импортозамещение) РПГ-М 220. За него я получил самую большую денежную премию 50 рублей. Что было примечательного?
      Это сортировка информации, хранящейся на лентах. Сначала информация готовилась на перфокартах, затем она переносилась на ленту в ручную отсортированном порядке. За тем в лентопротяжки ставились три бабины: одна с новыми данными, вторая с данными, подготовленными ранее и чистая на которую переносилась информация получаемая слиянием.
      Вы скажете какая древность. Но как были благодарны машинистки. К сожалению мы уже тогда начали отставать в развитии ЭВТ.
      Спасибо автору. Есть что вспомнить.

        0
        Сортировка слиянием — это дизельпанк :)
          +1

          А что сейчас ее не используют? В чем юмор-то?

            +1
            Я имел ввиду, что первые алгоритмы сортировок этого класса придуманы именно под железо середины XX века. Чего, в принципе, не скажешь про другие классы сортировок.

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

            Дизельпанк я, кстати, обожаю и к merge sort во всём её разнообразии тоже отношусь хорошо. Так что юмор самый доброжелательный.
              +1

              Вот и хорошо.

          +1
          Три бабины ставили бобины.
            +1

            Да, сплоховал я: в горящую избу войдет. Да, бобины, бобины ...

          +1
          Статься классная, и анимации дают наглядное представление, но что с кодом? В функции bose_nelson_merge вместо
           if m = 1:
              if data[j] > if data[j + r]:

          должно быть
           if m == 1:
              if data[j] > data[j + r]:

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

            Статью писал ночью, утром уже не было никаких сил вычитать код.
            0

            Наверно, в статью стоит добавить сложность второго алгоритма.

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

            Самое читаемое