Гномья сортировка

sorting_gnomesort_anim

С этой задачей мы уже сталкивались, когда решали задачи раздела "Цикл For и массивы. Решение тематических задач".

Итак, что же такое гномья сортировка. Википедия описывает её так: Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице Дика Груна Гномья сортировка:

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

Дик Грун

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

Для наглядности приведу ещё одну демонстрацию этого алгоритма:

sorting_gnomesort_anim

Ниже приведён код сортировки. Это оптимизированная версия с использованием промежуточной переменной ipos для запоминания того места, в котором встретились неотсортированные горшки, чтобы после окончания правильной расстановки всех предыдущих горшков разрешить прыжок вперёд, туда, где гном остановился до движения влево, избегая лишних итераций и сравнений. На рисунке выше показана как раз такая оптимизированная версия.

Задача та же, что и в сортировке методом пузырька: дан массив целых чисел. Необходимо отсортировать этот массив по возрастанию (т.е. расставить цифры по порядку от меньшего к большему). Программа получает на вход размер массива n, а затем сам массив. Необходимо вывести на экран отсортированный по возрастанию массив.

Решение:

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
 
procedure main is
    type Matrix is array(Integer range <>) of Integer;
    n : Integer;
    tmp : Integer;
    iprev, inext, ipos : Integer;
begin
    Put("Размер массива: ");
    Get(n);
    declare
        mas : Matrix(1..n);
    begin
        --ввод массива
        Put_Line("Массив: ");
        for i in 1..mas'Last loop
            Get(mas(i));
        end loop;
 
        --сортировка массива
        iprev := 1;
        inext := 2;
        while inext <= mas'Last loop
            --сравниваются 2 элемента, и если последующий меньше предыдущего, то
            if mas(inext) < mas(iprev) then
                ipos := inext;              --запоминаем позицию "следующего"
                --Сравниваем найденный элемент (меньший) со всеми элементами в массиве,
                --стоящими до него, и производим обмен, если элемент меньше предыдущего
                while inext - 1 >= 1 and then mas(inext) < mas(inext - 1) loop
                    tmp := mas(inext);
                    mas(inext) := mas(inext - 1);
                    mas(inext - 1) := tmp;
                    inext := inext - 1;
                end loop;
                inext := ipos;
            end if;
            inext := inext + 1;
            iprev := inext - 1;
        end loop;
 
        --вывод массива
        Put_Line("Итоговый массив: ");
        for i in 1..mas'Last loop
            Put(Item => mas(i), Width => 1);
            Put(" ");
        end loop;
    end;
end main;

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *