Объединить Сортировки

Сортировка слиянием работает следующим образом:

1. Просматриваются (или, как вариант, формируются) упорядоченные подмассивы.

2. Упорядоченные подмассивы объединяются в общий упорядоченный подмассив.

Но если в массиве мы найдем два упорядоченный подмассив, то это совсем другое дело.

Дело в том, что очень быстро и с минимальными затратами можно их объединить — сформировать из пары упорядоченных подмассивов общий упорядоченный подмассив.

Как видите, объединить два упорядоченных массива в один непросто, а очень просто.

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

Меньший элемент направляется в общий котел.

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

В этом суть алгоритмов этого класса.

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

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

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

Автором этой концепции является Джон фон Нейман.

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

Трудно оценить правдоподобность этой версии, поскольку его первая работа по сортировке слиянием датируется 1948 годом, а создание бомбы завершилось на 3 года раньше.

Однако какая там атомная сортировка, давайте разберемся.

Естественный синтез Неймана



На алгоритм Неймана повлияли особенности конструкции компьютеров 1940-х годов.

Это выглядело так:

1. Всего используются три магнитные ленты — основная, на которую записываются несортированные данные, и две вспомогательные.

2. Данные считываются последовательно с основной ленты.

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

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

   .

5. Шаги 2-4 повторяются еще раз, только данные переносятся на другую вспомогательную ленту.

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

6. Когда все данные считаны с основной ленты, обрабатываются вспомогательные ленты.

7. Данные считываются поочередно с обеих вспомогательных лент.
8. При этом очередные данные с двух лент сравниваются друг с другом.

   По результатам сравнения на основную ленту записывается меньший элемент пары.

9. Поскольку границы массивов на вспомогательных лентах отмечены указателями, чтение и сравнение происходит только внутри отсортированных подмассивов.

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

11. Повторяем весь процесс еще раз, пока данные на основной ленте не станут полностью упорядоченным массивом.

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

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

На примере этой первой сортировки слиянием мы уже видим недостаток этого класса алгоритмов — стоимость дополнительной памяти.

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

Прямой синтез Боуз-Нельсона Строго говоря, алгоритм Боуз-Нельсона — это сортировочная сеть, а не сортировка.

В процессе работы массив и все его подмассивы делятся пополам и ничто не мешает обрабатывать все эти половинки параллельно на всех этапах.

Однако это также можно представить в виде сортировки.

И когда-нибудь мы доберемся и до темы сортировки сетей.

1. Массив разделен пополам — на левую и правую половины.

2. Элементы разделены на группы.

3. На первой итерации это двойки элементов (1-й элемент левой половины + 1-й элемент правой половины, 2-й элемент левой половины + 2-й элемент правой половины и т.д.), на второй итерации - четверки элементы (1-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

   

Сначала происходит разделение, затем синтез.

Ссылки

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

• Приложение Excel AlgoLab.xlsm
• Сортировка бирж
• Сортировка вставкой
• Сортировка по выбору
• Объединить сортировки
  • Сбалансированное слияние сверху вниз и снизу вверх
  • Многофазная сортировка слиянием
  • Каскадная сортировка слиянием
  • Осциллирующая сортировка слиянием
  • Резьбовая и несмешивающаяся сортировка
  • Сравнение видов слиянием
• Сортировка по распространению
• Гибридные сорта

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

Сортировка Боуз-Нельсона имеет ограничение: размер массива должен быть степенью двойки.

Если это условие не выполнено, макрос усекает массив до подходящего размера.

Эта статья написана при поддержке EDISON Software, которая пишет программное обеспечение для 3D-реконструкции и занят разработка сложного измерительного оборудования .

• Вычисления В Промышленности

  19 Oct, 24

• Бесплатные Статьи: Вкусный Рецепт Построения Своего Бизнеса

  19 Oct, 24

• Google Купила Emu — Мессенджер С Функциями Виртуального Помощника

  19 Oct, 24

• Как Я Писал Интернет-Магазин В 15 Лет

  19 Oct, 24

• Полнотекстовый Поиск В Веб-Проектах: Sphinx, Apache Lucene, Xapian.

  19 Oct, 24

• Как Начать Карьеру В Игровой Индустрии

  19 Oct, 24

• Программирование И Музыка: Задержка, Искажения И Модуляция Параметров. Часть 4

  19 Oct, 24

• Drupal Views Прикрепите

  19 Oct, 24

• Прокси Только На Место

  19 Oct, 24

• Тамбов, Пятница, 15.00, Конференц-Зал Тгту

  19 Oct, 24