Быстрая сортировка
Автором так называемой "быстрой" сортировки является Хоар. Он назвал ее быстрой потому, что в общем случае эффективность этого алгоритма довольно высока. Идея метода следующая. Выбирается некоторый "барьерный" элемент, относительно которого мы разбиваем исходный список на два подсписка. В один мы помещаем элементы, меньшие барьерного элемента, во второй — большие либо равные. Каждый из этих списков мы сортируем тем же способом, после чего приписываем к списку тех элементов, которые меньше барьерного, вначале сам барьерный элемент, а затем — список элементов не меньших барьерного. В итоге получаем список, состоящий из элементов, стоящих в правильном порядке.
При воплощении в программный код этой идеи нам, как обычно, понадобится пара предикатов.
Вспомогательный предикат partition будет отвечать за разбиение списка на два подсписка. У него будет четыре аргумента. Первые два элемента — входные: первый — исходный список, второй — барьерный элемент. Третий и четвертый элементы — выходные, соответственно, список элементов исходного списка, которые меньше барьерного, и список, состоящий из элементов, которые не меньше барьерного элемента.
Предикат quick_sort будет реализовывать алгоритм быстрой сортировки Хоара. Он будет состоять из двух предложений. Правило будет осуществлять с помощью предиката partition разделение непустого списка на два подсписка, затем сортировать каждый из этих подсписков рекурсивным вызовом себя самого, после чего, используя предикат conc (созданный нами ранее), конкретизирует второй аргумент списком, получаемым объединением отсортированного первого подсписка и списка, сконструированного из барьерного элемента (головы исходного списка) и отсортированного второго подсписка. Запишем это:
quick_sort([],[]). /* отсортированный пустой список остается пустым списком */ quick_sort([H|T],O):– partition(T,H,L,G), /* делим список T на L (список элементов меньших барьерного элемента H) и G (список элементов не меньших H) */ quick_sort(L,L_s), /* список L_s — результат упорядочивания элементов списка L */ quick_sort(G,G_s), /* аналогично, список G_s — результат упорядочивания элементов списка G */ conc(L_s,[H|G_s],O). /* соединяем список L_s со списком, у которого голова H, а хвост G_s, результат обозначаем O */ partition([],_,[],[]). /* как бы мы ни делили элементы пустого списка, ничего кроме пустых списков не получим */ partition([X|T],Y,[X|T1],Bs):– X<Y,!, partition(T,Y,T1,Bs). /* если элемент X меньше барьерного элемента Y, то мы добавляем его в третий аргумент */ partition([X|T],Y,T1,[X|Bs]):– partition(T,Y,T1,Bs). /* в противном случае дописываем его в четвертый аргумент */
Прежде чем перейти к изучению следующего алгоритма сортировки, решим одну вспомогательную задачу.
Пусть у нас есть два упорядоченных списка, и мы хотим объединить их элементы в один список так, чтобы объединенный список также остался отсортированным.
Идея реализации предиката, осуществляющего слияние двух отсортированных списков с сохранением порядка, довольно проста. Будем на каждом шаге сравнивать головы наших упорядоченных списков и ту из них, которая меньше, будем переписывать в результирующий список. И так до тех пор, пока один из списков не закончится. Когда один из списков опустеет, нам останется дописать остатки непустого списка к уже построенному итогу. В результате получим список, состоящий из элементов двух исходных списков, причем элементы его расположены в нужном нам порядке.
Создадим предикат (назовем его fusion) реализующий приведенное описание. Так как мы не знаем, какой из списков опустеет раньше, нам необходимо "гнать" рекурсию сразу по обоим базовым спискам. У нас будет два факта — основания рекурсии, которые будут утверждать, что если мы сливаем некий список с пустым списком, то в итоге получим, естественно, тот же самый список. Причем этот факт имеет место и в случае, когда первый список пуст, и в случае, когда пуст второй список.
Шаг рекурсии нам дадут два правила: первое будет утверждать, что если голова первого списка меньше головы второго списка, то именно голову первого списка и нужно дописать в качестве головы в результирующий список, после чего перейти к слиянию хвоста первого списка со вторым. Результат этого слияния будет хвостом итогового списка. Второе правило, напротив, будет дописывать голову второго списка в качестве головы результирующего списка, сливать первый список с хвостом второго списка. Итог этого слияния будет хвостом объединенного списка.
fusion(L1,[ ],L1):–!. /* при слиянии списка L1 с пустым списком получаем список L1 */ fusion([ ],L2,L2):–!. /* при слиянии пустого списка со списком L2 получаем список L2 */ fusion([H1|T1],[H2|T2],[H1|T]):– H1<H2,!, /* если голова первого списка H1 меньше головы второго списка H2 */ fusion(T1, [H2|T2],T). /* сливаем хвост первого списка T1 со вторым списком [H2|T2] */ fusion(L1, [H2|T2],[H2|T]):– fusion(L1,T2,T). /* сливаем первый список L1 с хвостом второго списка T2 */
Теперь можно перейти к изучению алгоритма сортировки слияниями.