Ответ в теме: Сортировка методом выбора на Prolog

      Комментарии к записи Ответ в теме: Сортировка методом выбора на Prolog отключены
#2153

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

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

selection_sort(List, SortedList):-
  selection_sort(List, [], SortedList).
  
selection_sort([], SortedList, SortedList):-!.
selection_sort(UnSortedPart, SortedPart, SortedList):-
  min_list(UnSortedPart, MinElement),
  delete_single_element(UnSortedPart, MinElement, UnSortedTail),
  selection_sort(UnSortedTail, [MinElement|SortedPart], SortedList).

Если исходный список пуст, значит все элементы были отсортированы – необходимо вернуть их в качестве результата. Иначе из неупорядоченной части выбирается минимальный элемент, его значение удаляется из списка. В результате рекурсивной обработки остальных элементов формируется новый список, в начало которого необходимо добавить выделенный ранее минимум.