Сортировка списков. Список может быть отсортирован, если определено отношение упорядочения меж­ду элементами в списке

Список может быть отсортирован, если определено отношение упорядочения меж­ду элементами в списке. Для целей этого описания предполагается, что существует следующее отношение упорядочения: 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