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

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

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 12 мес. назад.

  • Автор
    Сообщения
  • #2138

    questioner
    Участник

    Помогите реализовать алгоритм сортировки выбором на языке Prolog.
    Согласно алгоритма, исходный список разделяется на уже обработанную и неупорядоченную части.
    На каждом шаге из необработанной части извлекается минимальный элемент, который добавляется в конец отсортированного списка.
    Более подробное описание алгоритма можно найти в статье про блок-схемы алгоритмов.

    selectsort_flowchart

  • #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).

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

Для ответа в этой теме необходимо авторизоваться.