Сортировка списков

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

В этой лекции речь пойдет о списках, элементами которых являются числа. Хотя в большинстве задач, которые будут рассматриваться, неважно, к какому домену относятся элементы списка, для определенности будем считать, что это целые числа.

Таким образом, списки, с которыми мы планируем работать, могут быть представлены в разделе описания доменов примерно следующим образом:

DOMAINS

Рекомендуемые материалы

listI = integer*

Для разминки решим несложный пример.

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

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

Так как в пустом списке элементов нет, сумма элементов пустого списка равна нулю. Для вычисления суммы элементов непустого списка нужно к сумме элементов хвоста добавить первый элемент списка. Запишем эту идею:

sum([], 0). /* сумма элементов пустого списка равна

               нулю */

sum([H|T], S) :–

           sum(T, S_T), /* S_T — сумма элементов хвоста */

           S = S_T + H. /* S — сумма элементов исходного

                           списка */

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

Еще один вариант данного предиката можно написать, используя накопитель. В нем будем хранить уже насчитанную сумму. Начинаем с пустым накопителем. Переходя от вычисления суммы непустого списка к вычислению суммы элементов его хвоста, будем добавлять первый элемент к уже насчитанной сумме. Когда элементы списка будут исчерпаны (список опустеет), передадим "накопленную" сумму в качестве результата в третий аргумент.

Запишем:

sum_list([],S,S). /* список стал пустым, значит

                     в накопителе — сумма элементов

                     списка */

sum_list([H|T],N,S) :–

             N_T=H+N,

                  /* N_T — результат добавления к сумме,

                     находящейся в накопителе, первого

                     элемента списка */

               sum_list(T,N_T,S).

                  /* вызываем предикат от хвоста T и N_T */

Если нам нужно вызвать предикат от двух аргументов, а не от трех, то можно добавить вспомогательный предикат:

sum2(L,S):–

        sum_list(L,0,S).

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

Разберем еще один простой пример.

Пример. Напишем предикат, вычисляющий среднее арифметическое элементов списка.

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

avg(L,A):–

        summa(L,S), /* помещаем в переменную S сумму

                       элементов списка */

        length(L,K), /* переменная K равна количеству

                        элементов списка */

        A=S/K. /* вычисляем среднее как отношение суммы

                  к количеству */

Единственная проблема возникает при попытке найти среднее арифметическое элементов пустого списка. Если мы попытаемся вызвать цель avg([],A), то получим сообщение об ошибке "Division by zero" ("Деление на ноль"). Это произойдет, потому что предикат length([],K) конкретизирует переменную K нулем, а при попытке достижения третьей подцели A=S/K и произойдет вышеупомянутая ошибка. Можно посчитать это нормальной реакцией предиката. Раз в пустом списке нет элементов, значит, нет и их среднего арифметического. А можно изменить этот предикат так, чтобы он работал и с пустым списком.

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

avg([],0):–!.

avg(L,A):–

        summa(L,S),

        length(L,K),

        A=S/K.

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

Пример. Создадим предикат, находящий минимальный элемент списка.

Как обычно, наше решение будет рекурсивным. Но так как для пустого списка понятие минимального элемента не имеет смысла, базис рекурсии мы запишем не для пустого, а для одноэлементного списка. В одноэлементном списке, естественно, минимальным элементом будет тот самый единственный элемент списка ("при всем богатстве выбора другой альтернативы нет!").

Шаг рекурсии: найдем минимум из первого элемента списка и минимального элемента хвоста — это и будет минимальный элемент всего списка.

Оформим эти рассуждения:

min_list([X],X). /* единственный элемент одноэлементного

                    списка является минимальным элементом

                    списка */

min_list([H|T],M):–

   min_list(T,M_T), /* M_T — минимальный элемент хвоста */

   min(H,M_T,M). /* M — минимум из M_T и первого элемента

                    исходного списка */

Обратите внимание на то, что в правиле, позволяющем осуществить шаг рекурсии, использован предикат min, подобный предикату max, который был разобран нами в третьей лекции.

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

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

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

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

Начнем с наиболее известного "пузырькового" способа сортировки. Его еще называют методом прямого обмена или методом простого обмена.

Пузырьковая сортировка

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

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

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

Основной предикат bubble будет осуществлять пузырьковую сортировку списка, используя вспомогательный предикат permutation.

permutation([X,Y|T],[Y,X|T]):–

                        X>Y,!.

                              /* переставляем первые два

                                 элемента, если первый больше

                                 второго */

permutation([X|T],[X|T1]):–

                        permutation(T,T1).

                              /*переходим к перестановкам

                                в хвосте*/

bubble(L,L1):–

     permutation(L,LL), /* вызываем предикат,

                           осуществляющий перестановку */

     !,

     bubble(LL,L1). /* пытаемся еще раз отсортировать

                       полученный список */

bubble(L,L). /* если перестановок не было, значит список

                отсортирован */

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

Сортировка вставкой

Теперь рассмотрим сортировку вставкой. Она основана на том, что если хвост списка уже отсортирован, то достаточно поставить первый элемент списка на его место в хвосте, и весь список будет отсортирован. При реализации этой идеи создадим два предиката.

Задача предиката insert — вставить значение (голову исходного списка) в уже отсортированный список (хвост исходного списка), так чтобы он остался упорядоченным. Его первым аргументом будет вставляемое значение, вторым — отсортированный список, третьим — список, полученный вставкой первого аргумента в нужное место второго аргумента так, чтобы не нарушить порядок.

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

ins_sort([ ],[ ]). /* отсортированный пустой список

                      остается пустым списком */

ins_sort([H|T],L):–

                  ins_sort(T,T_Sort),

                       /* T — хвост исходного списка,

                          T_Sort — отсортированный хвост

                          исходного списка */

                  insert(H,T_Sort,L).

                       /* вставляем H (первый элемент

                          исходного списка)в T_Sort,

                          получаем L (список, состоящий

                          из элементов исходного списка,

                          стоящих по неубыванию) */

insert(X,[],[X]). /* при вставке любого значения в пустой

                     список, получаем одноэлементный

                     список */

insert(X,[H|T],[H|T1]):–

                   X>H,!, /* если вставляемое значение

                             больше головы списка, значит

                             его нужно вставлять в хвост */

                   insert(X,T,T1).

                        /* вставляем X в хвост T,

                           в результате получаем

                           список T1 */

insert(X,T,[X|T]). /* это предложение (за счет отсечения

                      в предыдущем правиле) выполняется,

                      только если вставляемое значение

                      не больше головы списка T, значит,

                      добавляем его первым элементом

                      в список T */

Сортировка выбором

Идея алгоритма сортировки выбором очень проста. В списке находим минимальный элемент (используя предикат min_list, который мы придумали в начале этой лекции). Удаляем его из списка (с помощью предиката delete_one, рассмотренного в предыдущей лекции). Оставшийся список сортируем. Приписываем минимальный элемент в качестве головы к отсортированному списку. Так как этот элемент был меньше всех элементов исходного списка, он будет меньше всех элементов отсортированного списка. И, следовательно, если его поместить в голову отсортированного списка, то порядок не нарушится.

Запишем:

choice([ ],[ ]). /* отсортированный пустой список

                    остается пустым списком */

choice(L,[X|T]):– /* приписываем X (минимальный элемент

                     списка L) к отсортированному

                     списку T */

                min_list(L,X), /* X — минимальный элемент

                                  списка L */

                delete_one(X,L,L1),

                               /* L1 — результат удаления

                                       первого вхождения

                                       элемента X из списка L */

                choice(L1,T). /* сортируем список L1,

                                 результат обозначаем T */