Пузырьковая сортировка
Идея этого метода заключается в следующем. На каждом шаге сравниваются два соседних элемента списка. Если оказывается, что они стоят неправильно, то есть предыдущий элемент меньше следующего, то они меняются местами. Этот процесс продолжаем до тех пор, пока есть пары соседних элементов, расположенные в неправильном порядке. Это и будет означать, что список отсортирован.
Аналогия с пузырьком вызвана тем, что при каждом проходе минимальные элементы как бы "всплывают" к началу списка.
Реализуем пузырьковую сортировку посредством двух предикатов. Один из них, назовем его 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 переходит от правила к факту и возвращает в качестве второго аргумента отсортированный список.
