Gnome Sort Начальный

Gnome Sort

Урок 11 из 14 в курсе Алгоритмы. Старт.

Содержание курса (11/14)
1 Bubble Sort 2 Insertion Sort 3 Selection Sort 4 Merge Sort 5 Quick Sort 6 Heap Sort 7 Shell Sort 8 Counting Sort 9 Cocktail Sort 10 Comb Sort
11 Gnome Sort
12 Odd-Even Sort 13 Pancake Sort 14 Radix Sort

Interactive

Gnome Sort Visualizer

Введите числа и управляйте пошаговым выполнением алгоритма.

sorting

История шагов

Gnome Sort

Gnome Sort — простой алгоритм, в котором "садовый гном" двигается по массиву и при необходимости делает шаг назад.

Основная идея

Идём вперёд, пока пары соседей упорядочены. Если нашли неупорядоченную пару — меняем местами и шагаем назад.

Пошаговый пример

Исходный массив:

[4, 2, 5, 1, 3]
  1. Сравниваем 4 и 2 → меняем и идём назад
  2. Дальше двигаемся вперёд, пока пары упорядочены
  3. Каждый "шаг назад" возвращает элемент на своё место

Псевдокод

i = 0
while i < n:
    if i == 0 or arr[i - 1] <= arr[i]:
        i += 1
    else:
        swap(arr[i - 1], arr[i])
        i -= 1

Оптимизация: По сути упрощённая версия insertion sort без вложенных циклов.

Сложность

Время O(n²) в среднем и худшем, O(n) на почти отсортированных данных.
Память O(1), in-place.

Когда используется

  • Обучение
  • Очень маленькие массивы
  • Демонстрация одношагового подхода

Ключевые свойства

  • Стабильный
  • In-place
  • Очень простой код
Все уроки курса

Комментарии к уроку

Войдите, чтобы оставить комментарий.

Пока нет комментариев — будьте первым.