Ответ в теме: Алгоритм сортировки подсчетом на Prolog

      Комментарии к записи Ответ в теме: Алгоритм сортировки подсчетом на Prolog отключены
#1955

Алгоритм сортировки подсчетом на вход кроме списка принимает границы интервала [A, B], в котором находятся сортируемые числа.
Алгоритм создает упорядоченный набор контейнеров со значениями от A до B, раскладывает по ними числа массива (подсчитывает количество вхождений каждого элемента), а затем соединяет результаты.

enumeration_sort(List, A, B, SortedList):-
  create_boxes(A, B, EmptyBoxes), 
  fill_boxes(List, EmptyBoxes, Boxes), 
  boxes_to_list(Boxes, SortedList).

В качестве контейнера можно использовать кортеж/пару — (Value, Counter). Функция create_boxes должна создать упорядоченный по значению список таких пар для всех элементов от A до B, при этом задав значение Counter равным нулю.

create_boxes(A, B, []):-
  A > B, !.
create_boxes(A, B, [(A, 0)|Boxes]):-
  NextA is A + 1, 
  create_boxes(NextA, B, Boxes).

Если A > B, то функция не должна создавать ни одной пары, поэтому возвращает пустой список. В остальных случаях она увеличивает значение левой границы, рассчитывает рекурсивно контейнеры для уменьшенного интервала и добавляет к полученному результату кортеж (A, 0).

Функция подсчета (размещения элементов по ящикам) должна:

  1. получить первый элемент списка (E);
  2. найти в списке ящик со значением E и увеличить счетчик в нем
  3. обработать рекурсивно остальные элементы списка

Однако, на Prolog мы не можем изменить значение элемента списка — придется создать новый список с единственным измененным элементом. Чтобы создать новый список надо будет получить элементы, расположенные «слева» и «справа» от изменяемого — для этого можно применить функцию разделения списка divide_list.

fill_boxes([], Boxes, Boxes):-!.
fill_boxes([Head|Tail], Buffer, Boxes):-
  divide_list(Buffer, [LeftPart, [(Head, Num)], RightPart]), !, 
  NextNum is Num + 1,
  append(LeftPart, [(Head, NextNum)|RightPart], NewBuffer),
  fill_boxes(Tail, NewBuffer, Boxes), !.

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

Остается преобразовать ящики в отсортированный список:

boxes_to_list([], []):-!.
boxes_to_list([(_Head, 0)|TailBoxes], List):-
  !, boxes_to_list(TailBoxes, List).
boxes_to_list([(Head, Num)|TailBoxes], [Head|ListTail]):-
  NextNum is  Num - 1, 
  boxes_to_list([(Head, NextNum)|TailBoxes], ListTail).

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