Советы, трюки и секреты для Blogger.com блоггеров. Все для Blogspot. Советы, трюки и секреты для Blogger.com блоггеров. Все для Blogspot.

Сортировка списков (prolog)

11 декабря 2009, 23:26

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

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

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

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

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

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

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

Быстрая сортировка

Идея метода следующая. Выбирается некоторый «барьерный» элемент, относительно которого мы разбиваем исходный список на два подсписка. В один мы помещаем элементы, меньшие барьерного элемента, во второй — большие либо равные. Каждый из этих списков мы сортируем тем же способом, после чего приписываем к списку тех элементов, которые меньше барьерного, вначале сам барьерный элемент, а затем — список элементов не меньших барьерного. В итоге получаем список, состоящий из элементов, стоящих в правильном порядке.

Сортировка слияниями

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

Решение:

Сортировка списков (prolog)