Теоретическая часть. 
Разработка программы сортировки одномерного массива с помощью гномьей сортировки

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков.

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

Дик Грун Алгоритм концептуально простой, не требует вложенных циклов. Время работы {displaystyle Oleft (n^{2} ight)}. На практике алгоритм может работать так же быстро, как и сортировка вставками.

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

Пример: массив сортировка генератор тестирование Если мы хотим отсортировать массив с элементами [4] [2] [7] [3] от большего к меньшему, то на итерациях цикла while будет происходить следующее:

• · [4] [2] [7] [3] (начальное состояние: i == 1, j == 2);
• · [4] [2] [7] [3] (ничего не произошло, но сейчас i == 2, j == 3);
• · [4] [7] [2] [3] (обмен a[2] и a[1], сейчас i == 1, а j == 3 по-прежнему);
• · [7] [4] [2] [3] (обмен a[1] и a[0], сейчас i == 3, j == 4);
• · [7] [4] [3] [2] (обмен a[3] и a[2], сейчас i == 2, j == 4);
• · [7] [4] [3] [2] (ничего не произошло, но сейчас i == 4, j == 5);
• · цикл закончился, т. к. i не < 4.