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

Гномья сортировка
Иллюстрация действия алгоритма гномьей сортировки

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

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

Алгоритм концептуально простой, не требует вложенных циклов. Время работы O\left(n^2\right). На практике алгоритм может работать так же быстро, как и сортировка вставками.

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

Описание

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

gnomeSort(a[0..size - 1])
    i = 1;
    j = 2;
    while i < size
        if a[i - 1] <= a[i] //для сортировки по убыванию поменяйте знак сравнения на >=
            i = j;
            j = j + 1;
        else
            swap a[i - 1] and a[i]
            i = i - 1;
            if i == 0
                i = j;
                j = j + 1;

Пример:

Если мы хотим отсортировать массив с элементами [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.

Оптимизация

В результате оптимизации гномья сортировка естественно трансформируется в сортировку вставками. Каждый раз «гном» наталкивается на новый номер, все значения слева от «гнома» уже отсортированы.


Wikimedia Foundation. 2010.

Поможем со сдачей теста

Полезное


Смотреть что такое "Гномья сортировка" в других словарях:

  • Сортировка Шелла — (англ. Shell sort)  алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными… …   Википедия

  • Сортировка выбором — (Selection sort)  алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… …   Википедия

  • Сортировка вставками — Сортировка вставками  простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ: эффективен на небольших наборах данных, на наборах данных до …   Википедия

  • Сортировка пузырьком — Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort)  простой алгоритм сортировки. Для понимания и реализации этот алгоритм  простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).… …   Википедия

  • Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в)… …   Википедия

  • Сортировка перемешиванием — (Шейкерная сортировка) (англ. Cocktail sort) разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства. Во первых, если при движении по части массива перестановки не происходят, то эта… …   Википедия

  • Сортировка расчёской — (англ. comb sort)  это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine …   Википедия

  • Сортировка слиянием — Действие алгоритма на примере сортировки случайных точек. Сортировка слиянием (англ. merge sort) алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только п …   Википедия

  • Сортировка с помощью двоичного дерева — Пример двоичного дерева Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. …   Википедия

  • Устойчивая сортировка — Устойчивая (стабильная) сортировка  сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Устойчивость является очень важной характеристикой алгоритма сортировки, но, тем не менее, она… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»