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

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

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

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

    questioner
    Участник

    Нужно реализовать алгоритм сортировки подсчетом для списка целых чисел, находящихся в заданном диапазоне.
    Суть алгоритма в том, что программа сразу создает список из всех возможных элементов (диапазон ведь известен), а затем считает сколько раз каждое значение встретилось в сортируемом списке.

  • #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).

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

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