Сортировка слияниями
Метод слияний — один из самых "древних" алгоритмов сортировки. Его придумал Джон фон Нейман еще в 1945 году. Идея этого метода заключается в следующем. Разобьем список, который нужно упорядочить, на два подсписка. Упорядочим каждый из них этим же методом, после чего сольем упорядоченные подсписки обратно в один общий список.
Для начала создадим предикат, который будет делить исходный список на два. Он будет состоять из двух фактов и правила. Первый факт будет утверждать, что пустой список можно разбить только на два пустых подсписка. Второй факт будет предлагать разбиение одноэлементного списка на тот же одноэлементный список и пустой список. Правило будет работать в случаях, не охваченных фактами, т.е. когда упорядочиваемый список содержит не менее двух элементов. В этой ситуации мы будем отправлять первый элемент списка в первый подсписок, второй элемент — во второй подсписок, и продолжать распределять элементы хвоста исходного списка.
splitting([],[],[])./* пустой список можно расщепить только на пустые подсписки */ splitting([H],[H],[]). /* одноэлементный список разбиваем на одноэлементный список и пустой список */ splitting([H1,H2|T],[H1|T1],[H2|T2]):– splitting(T,T1,T2). /* элемент H1 отправляем в первый подсписок, элемент H2 — во второй подсписок, хвост T разбиваем на подсписки T1 и T2 */
Теперь можно приступать к записи основного предиката, который, собственно, и будет осуществлять сортировку списка. Он будет состоять из трех предложений. Первое будет декларировать очевидный факт, что при сортировке пустого списка получается пустой список. Второе утверждает, что одноэлементный список также уже является упорядоченным. В третьем правиле будет содержаться суть метода сортировки слиянием. Вначале список расщепляется на два подсписка с помощью предиката splitting, затем каждый из них сортируется рекурсивным вызовом предиката fusion_sort, и, наконец, используя предикат fusion, сливаем полученные упорядоченные подсписки в один список, который и будет результатом упорядочивания элементов исходного списка.
Запишем изложенные выше соображения.
fusion_sort([],[]):–!./* отсортированный пустой список остается пустым списком */ fusion_sort([H],[H]):–!. /* одноэлементный список упорядочен */ fusion_sort(L,L_s):– splitting(L,L1,L2), /* расщепляем список L на два подсписка */ fusion_sort(L1,L1_s), /* L1_s — результат сортировки L1 */ fusion_sort(L2,L2_s), /* L2_s — результат сортировки L2 */ fusion(L1_s,L2_s,L_s). /* сливаем L1_s и L2_s в список L_s */
Фактически этот алгоритм при прямом проходе дробит список на одноэлементные подсписки, после чего на обратном ходе рекурсии сливает их двухэлементные списки. На следующем этапе сливаются двухэлементные списки и т.д. На последнем шаге два подсписка сливаются в итоговый, отсортированный список.
В качестве завершения темы сортировки разработаем предикат, который будет проверять, является ли список упорядоченным. Это совсем не сложно. Для того чтобы список был упорядоченным, он должен быть либо пустым, либо одноэлементным, либо любые два его соседних элемента должны быть расположены в правильном порядке. Запишем эти рассуждения.
sorted([ ]). /* пустой список отсортирован */ sorted([_])./* одноэлементный список упорядочен */ sorted([X,Y|T]):– X<=Y, sorted([Y|T]). /* список упорядочен, если первые два элемента расположены в правильном порядке и список, образованный вторым элементом и хвостом исходного, упорядочен */
