Сортировка пузырьком (обменами) на Prolog

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

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

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

    questioner
    Участник

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

    Алгоритм имеет квадратичную сложность.

    bubblesort_flowchart Блок-схема алгоритма сортировки пузырьком.

  • #2152

    В алгоритме сортировки пузырьком содержится два цикла:

    • внутренний перебирает все пары соседних элементов в списке и переставляет их если порядок нарушен;
    • внешний вызывает внутренний цикл до тех пор, пока в списке есть пара элементов, нарушающая порядок

    Можно мысленно разделить список на сортированную и необработанную части — тогда после обработки внутреннего цикла один элемент должен попадать — наибольший элемент гарантированно вытеснится в конец списка:

    move_max_to_end([], []):-!.
    move_max_to_end([Head], [Head]):-!.
    move_max_to_end([First, Second|Tail], [Second|ListWithMaxEnd]):-
      First > Second, !,
      move_max_to_end([First|Tail], ListWithMaxEnd).
    move_max_to_end([First, Second|Tail], [First|ListWithMaxEnd]):-
      move_max_to_end([Second|Tail], ListWithMaxEnd).

    Если исходный список содержит менее двух элементов — то его наибольший элемент уже расположен в конце. В противном случае необходимо разделить его на два первых элемента (First, Second) и остальные (Tail). Из двух элементов надо выбрать наибольший и передать его для рекурсивной обработки, меньший элемент будет дописан в начало, полученного в результате списка.
    Таким образом, наибольший элемент продвигается в конец списка, остается вызывать эту функцию до тех пор, пока вызов изменяет данные, в противном случае список уже является упорядоченным:

    bubble_sort(SortedList, SortedList):-
      move_max_to_end(SortedList, DoubleSortedList),
      SortedList = DoubleSortedList, !.
    bubble_sort(List, SortedList):-
      move_max_to_end(List, SortedPart),
      bubble_sort(SortedPart, SortedList).

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

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