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

Просмотр 1 ветки ответов
  • Автор
    Сообщения
    • #2082
      @questioner

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

      quick-sort

    • #2084
      @admin

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

      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 список разделяется на две части. Все элементы в левой части гарантированно меньше элементов второй части, поэтому после их рекурсивной сортировки мы можем использовать обычное соединение списков, при котором «больший» список дописывается в конец «меньшего».

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