Сортировка слиянием на Prolog

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

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

    questioner
    Участник

    Помогите реализовать на Прологе алгоритм сортировки слиянием.

    Суть алгоритма заключается в том, что на каждом шаге исходный массив разделяется на 2 части, которые сортируются независимо друг от друга, а затем результаты объединяются.

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

  • #2081

    Алгоритм сортировки слиянием подробно описан и проанализирован.

    merge_sort

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

    mergeSort([], []):-!.
    mergeSort([SingleElement], [SingleElement]):-!.
    mergeSort(List, SortedList):-
      split(List, Part1, Part2),
      mergeSort(Part1, SortedPart1),
      mergeSort(Part2, SortedPart2),
      rangConcat(SortedPart1, SortedPart2, SortedList).

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