Сортировка выбором
Идея алгоритма сортировки выбором очень проста. В списке находим минимальный элемент (используя предикат 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 */
