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

      Комментарии к записи Ответ в теме: Сортировка пузырьком (обменами) на Prolog отключены
#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).

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