Сортировка вставками (методом простого включения)

      Комментарии к записи Сортировка вставками (методом простого включения) отключены

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

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

    questioner
    Участник

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

    insertsort_flowchart

  • #2143

    Для реализации сортировки понадобится функция вставки элемента в упорядоченный список:

    insert(Element, [], [Element]):-!.
    insert(Element, [Head|Tail], [Element, Head|Tail]):-
    Element < Head, !.
    insert(Element, [Head|Tail], [Head|InsertTail]):-
    insert(Element, Tail, InsertTail).

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

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

    insertion_sort(List, SortedList):-
    insertion_sort(List, [], SortedList).
    insertion_sort([], SortedList, SortedList):-!.
    insertion_sort([Head|Tail], SortedPart, SortedList):-
    insert(Head, SortedPart, SortedPartWithHead),
    insertion_sort(Tail, SortedPartWithHead, SortedList).

    Если элементы в необработанной части закончились — функция возвращает упорядоченную часть в качестве результата.
    В противном случае первый элемент неупорядоченной части вставляется в отсортированную при помощи функции insert. Полученный в результате список обрабатывается рекурсивно.

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