Створити предикати, що дозволяють здійснити сортування списків складаються з чисел. Ще одне завдання по РЛП, інші ви можете знайти тут.
Ідея цього методу полягає в наступному. На кожному кроці порівнюються два сусідні елементи списку. Якщо виявляється, що вони стоять неправильно, тобто попередній елемент менше наступного, то вони міняються місцями. Цей процес продовжуємо до тих пір, поки є пари сусідніх елементів, розташовані в неправильному порядку. Це і буде означати, що список відсортований. Реалізуємо бульбашкову сортування за допомогою двох предикатів. Один з них, назвемо його permutation, буде порівнювати два перших елемента списку і в разі, якщо перший виявиться більше другого, міняти їх місцями. Якщо ж перша пара розташована в правильному порядку, цей предикат буде переходити до розгляду хвоста. Основний предикат bubble буде здійснювати бульбашкову сортування списку, використовуючи допоміжний предикат permutation.
Сортування вставкою заснована на тому, що якщо хвіст списку вже відсортований, то досить поставити перший елемент списку на його місце в хвості, і весь список буде відсортований.
Ідея алгоритму сортування вибором дуже проста. У списку знаходимо мінімальний елемент. Видаляємо його зі списку. Що залишився список сортуємо. Приписуємо мінімальний елемент в якості голови до відсортовані списку. Так як цей елемент був менше всіх елементів вихідного списку, він буде менше всіх елементів відсортованого списку. І, отже, якщо його помістити в голову відсортованого списку, то порядок не порушиться.
Ідея методу наступна. Вибирається деякий «бар'єрний» елемент, щодо якого ми розбиваємо вихідний список на два подсписка. В один ми поміщаємо елементи, менші бар'єрного елемента, в другій - великі або рівні. Кожен з цих списків ми сортуємо тим же способом, після чого приписуємо до списку тих елементів, які менше бар'єрного, спочатку сам бар'єрний елемент, а потім - список елементів не менших бар'єрного. В результаті отримуємо список, що складається з елементів, що стоять в правильному порядку.
Ідея цього методу полягає в наступному. Розіб'ємо список, який потрібно впорядкувати, на два подсписка. Впорядкуємо кожен з них цим же методом, після чого злити впорядковані підсписки назад в один загальний список.