Сортировка списков. Список может быть отсортирован, если определено отношение упорядочения между элементами в списке
Список может быть отсортирован, если определено отношение упорядочения между элементами в списке. Для целей этого описания предполагается, что существует следующее отношение упорядочения: gt{ х, Y)
которое означает, что х больше Y, независимо от того, какой смысл вкладывается в понятие "больше". Если рассматриваемыми элементами являются числа, то отношение дг может быть, по всей вероятности, определено следующим образом: gt ( X, Y) : - Х>У.
Если же элементы представляют собой атомы, то отношение gt может соответствовать лексикографическому упорядочению, например, определенному как:
gtl X, Y) :- Х@>¥,
Напомним, что это отношение упорядочивает также составные термы. Предположим, что терм
sort! List, Sorted)
обозначает отношение, где List является списком элементов, a Sorted — списком тех же элементов, отсортированным в порядке возрастания в соответствии с отноше-
нием gt. В данной главе рассматриваются три определения этого отношения на языке Prolog, которые основаны на разных принципах сортировки списков. Ниже описан первый принцип.
Для сортировки списка List необходимо выполнить следующее:
■ найти в списке List два смежных элемента, X и Y, таких, что отношение gt { X, У] принимает истинное значение, и поменять местами х и Y в списке List, получив при этом список Listl; после этого отсортировать Listl;
■ если в списке List нет ни одной пары смежных элементов, X и Y, таких, что отношение gt ( X, Y) принимает истинное значение, то список List уже отсортирован.
Результатом перестановки местами двух элементов, X и Y, которые занимают неправильное положение по отношению друг к другу, является то, что после этой перестановки новый список в большей степени напоминает отсортированный список. После достаточного количества перестановок в конечном итоге должно быть достигнуто такое состояние, в котором все элементы занимают правильные положения. Такой принцип сортировки известен под названием пузырьковой сортировки (bubble sort). Поэтому соответствующей процедуре Prolog, приведенной ниже, будет присвоено название bubblesort.
bubblesort ( List, Sorted) ;-
swap( List, Listl), !, i Есть ли допустимая перестановка в списке List?
bubblesort ( Listl, Sorted).
bubblesort ( Sorted, sorted). % В противном случае список уже отсортирован
s»ap( [X, Y | Rest], [y, X | Rest]) :- * Поменять местами первые два элемента
gt( X, X).
swapf [Z I Rest], [Z 1 Restl]) :- % Поменять местами элемента в хвосте
swap; Rest, Restl) .
Еще одним простым алгоритмом сортировки является сортировка вставкой, которая основана на описанном ниже принципе.
Чтобы отсортировать непустой список, L . [X | Т], необходимо выполнить следующее.
1. Отсортировать хвост Т списка L.
2. Вставить голову X списка L в отсортированный хвост списка, в такую позицию, чтобы результирующий список оставался отсортированным. В результате будет получен весь отсортированный список.
Такую постановку задачи можно перевести на язык Prolog в виде следующей процедуры insert sort:
insertsort ( [],П>-
insertsort! [X I Tail], Suited):-
insertsort ( Tail, SortedTa.il), % Отсортировать хвост списка
insert!X, SortedTail,Sorted). Ъ Вставить хв надлежащем месте
insert tx, [Y ! Sorted], [Y ; Sortedl]) :-
gt< x, Y), !,
insertf X, Sorted, Sortedl). insert! x, Sorted, [X I Sorted]).
Глава Э. Операции со структурами данных
Процедуры сортировки bubblesorr и insertsort являются простыми, но неэффективными. Из этих двух процедур сортировка вставкой (insertsort)является более эффективной. По среднее время, необходимое для сортировки списка длиной п с помощью процедуры inserzsort, возрастает пропорционально г/. Поэтому для сортировки длинных списков предусмотрен гораздо более эффективный алгоритм сортировки — quicksort. Он основан на следующем принципе, который иллюстрируется на рис. 9.1.
[5,3,7,8,1,4,7,61
i
удалить Х(Х = 51
[3,7,В,1,4,7,6]
 | |||||
| | |||||
 | |
| разбиение |
| ,'1!>(>;'-!И L |
все элементы £ 5
[3,1,4]
| ъ |
сортировать
[1,3,4]
I
| i не:n nmiMOHTbi | >5 |
| [7,8,7,6] | |
| 1сортире | |
| [ 6.7,7,8] |
$
выполнить конкатенацию
V
1,3,4,5,6,7,7,8
Рис- 9Л Сортировки списка с помощью алгоритма
quicksort
Описание алгоритма quicksort приведено ниже.
Чтобы отсортировать непустой список L, необходимо выполнить следующие действия.
1. Удалить некоторый элемент X из списка L и разбить остаток L на два списка, называемые Small и Big, следующим образом: перенести все элементы списка L, которые больше X, в список Big, а все остальные — в список Small.
2. Отсортировать список Small, получив список SortedSmall.
3. Отсортировать список Big, получив список SortedBig.
4. Весь отсортированный список представляет собой конкатенацию списков
SortedSmall и [X | SortedBig}.
Если сортируемый список пуст, то результатом сортировки также является пустой список. Реализация процедуры quicksort на языке Prolog приведена в листин-
Часть I. Язык Prolog
ре 9.1. Характерной особенностью этой реализации является то, что элемент X, удаляемый из списка L, всегда представляет собой голову списка L. Операция разбиения списка программируется в виде следующего отношения с четырьмя параметрами: split; X, L, Small, Big)
Сложность этого алгоритма, определяемая затратами времени на выполнение, зависит от того, насколько удачно происходит разбиение сортируемого списка. Если список разбивается на два списка, имеющих приблизительно равную длину, то затраты времени на выполнение этой процедуры сортировки пропорциональны п log л, где я — длина сортируемого списка. Если, вопреки ожиданиям, разбиение всегда приводит к тому, что один список становится больше другого, то затраты времени становятся пропорциональными ;г . Но, к счастью, исследования показали, что средняя производительность процедуры quicksort ближе к наилучшему варианту, чем к наихудшему.
Программу, приведенную в листинге 9.1, можно дополнительно усовершенствовать, применив лучшую реализацию операции конкатенации. Благодаря использованию представления списков в виде разностных пар, описанного в главе 8, операция конкатенации становится тривиальной. Для применения этой идеи в рассматриваемой процедуре сортировки списки, применяемые в листинге 9.1, можно представить в виде пары списков в форме A-Z следующим образом;
SortedSmall представлен как A1-Z1 SortedBig представлен как A2-Z2
Л ИСТИ НГ 9.1. Процедура быстрой сортировки quicksort
?''qaic):sort7List,'soitedListr:........................
% сортироька списка List с применением алгоритма quicksort quicksort! [], [] ) .
quick s SortedSmall 3 , or [X tedSm ,Ei3,. Sorted).
split (x, [ ] , [ ] , [ 1) .
Split; X, [YITail], [ Y | Small] , Big) :-gt( x, Y) , !, split! X, Tail, Small, Big).
Split! X, [Y|Tail), Small, [YjBigU :-split! X, Tail, Small, Big;.
Таким образом, конкатенация списков SortedSmall и [X | SortedBig] соответствует конкатенации следующих пар:
А1 - Z1 и [X | А2] - Z2
Список, полученный в результате конкатенации, представляется с помощью следующего выражения:
AI- Z2, 1 до Z2 - [X | А2]
Пустой список представлен любой парой Z-Z. В результате систематического внесения этих изменений в программу (см. листинг 9.1) получена более эффективная реализация процедуры quicksort, запрограммированная в виде quicksort2 в листинге 9.2. В процедуре quicksort все еще используется обычное представление списков, но сортировка фактически выполняется более эффективной процедурой
Глава Э. Операции со структурами данных
quicksort2, в которой применяется представление списков в виде разностных пар. Отношение между этими двумя процедурами выглядит следующим образом:
quicksort Г L, S! :-
quicksorts t L, S - I ]) ,
Листинг 9.2. Более эффективная реализация процедуры q u i c ks o rt с использованием представления списков в виде разностных пар; отношение s p l i t ( x, List, small, Big) приведено в листинге 9.1
'■■ quicksort ( List, SortedList) :
сортировка списка List с применением алгоритма quicksort
quicksort': List, Sorted) :-
quickscrt2 ( list, Sorted - [) ).
\ quicksort2 ( List, SortedDiffList) : сортировка списка List,- результат % представлен как разностный список
quicksort2 ( J.l , Z - Z} .
quicksort2( [У. Tail), 7U - Z2) :-split( X, Tail, Small, Big) , quicksorts ! Small, Al - .:■: A2 ] ), quicksort2 I eiq, A2 - Z2).
Упражнения
9.1. Напишите процедуру для слияния двух отсортированных списков и получения
третьего списка, например, следующим образом:
?- raerqef [2,5,6,6,8], [1,3,5,9], L) . L = [1,2,3,3,5,6, "3,6,5]
9.2. Различие между программами сортировки, приведенными в листингах 9.1 и 9.2, состоит в том, что используются иные представления списков, — в последней применяются разностные списки. Процедура преобразования обычных списков в разностные является простой и может выполняться механически. В качестве упражнения систематически внесите соответствующие изменения в программу, приведенную в листинге 9.1, чтобы преобразовать ее в программу, которая показана в листинге 9.2.
9.3. Рассматриваемая программа quicksort обнаруживает низкую эффективность, если сортируемый список уже полностью отсортирован или почти отсортирован. Объясните, с чем это связано.
9.4. Еще один перспективный принцип сортировки списков, позволяющий устранить указанный выше недостаток процедуры quicksort, основан на том, что список делится на части, после чего меньшие списки сортируются, а затем эти отсортированные меньшие списки сливаются. В соответствии с этим, чтобы отсортировать список _, необходимо выполнить следующее:
• разделить список: на два списка, L1 и L2, приблизительно равной длины;
• отсортировать L1 и L2, получив списки S1 и S2;
• выполнить слияние списков S1 и S2 и получить отсортированный список L.
Такой алгоритм известен под названием алгоритма сортировки - слияния. Реализуйте алгоритм сортировки-слияния и сравните эффективность полученной программы с программой quicksort.
196 Часть I. Язык Prolog