Быстрая сортировка на Prolog

      Комментарии к записи Быстрая сортировка на Prolog отключены

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

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

    questioner
    Участник

    Помогите написать функцию быстрой сортировки списка на Prolog.
    Согласно алгоритма, из исходного списка по какому-либо принципу выделяется опорный элемент (Pivot), относительно которого массив разделяется на две части. В первую часть помещаются элементы, большие заданного, а во вторую — остальные (я нашел готовую функцию на форуме).
    Каждая часть сортируется рекурсивно, т.е. выполняется деление списка на 2 части, т.е. задача упрощается. Если длина списка меньше двух, то список уже отсортирован и его не требуется делить. Отсортированные части необходимо объединить.

    quick-sort

  • #2084

    Более подробное описание и асимптотические анализ алгоритма быстрой сортировки можно посмотреть в специальной статье.

    qsort([], []).
    qsort([Elem], [Elem]).
    qsort([Pivot|Tail], SortedList):-
    divide(Tail, Pivot, GreaterList, SmallerList),
    qsort(GreaterList, SortedGreaterList),
    qsort(SmallerList, SortedSmallerList),!,
    append(SortedSmallerList, [Pivot|SortedGreaterList], SortedList).

    Первое правило обрабатывает случай, когда на вход подан пустой список, а второе обрабатывает список из одного элемента. Такие списки уже отсортированы, поэтому результатом является точно такой же список.
    В противном случае из списка выделяется первый элемент, который берется в качестве опорного, функцией divide список разделяется на две части. Все элементы в левой части гарантированно меньше элементов второй части, поэтому после их рекурсивной сортировки мы можем использовать обычное соединение списков, при котором «больший» список дописывается в конец «меньшего».

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