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

Интерактивная анимация

Идея гномьей (наивной) сортировки такова. Представим, что числа — это горшочки. Гном начинает проверять горшочки слева направо. Пока они упорядочены по возрастанию, он просто продолжает проверять дальше. Как только он встречает горшок, который не на своём месте, он постепенно возвращается влево, находя ему подходящее место. Как только горшочек поставлен куда нужно, гном продолжает идти вправо.

function gnomeSort(data[], size)
{
for (i = 0; i < size; )
{
if (i == 0 or data[i - 1] <= data[i])
{
++i;
}
else
{
swap(data[i], data[i - 1]);
--i;
}
}
}

Шаг → Перезапуск Перезапуск (худший случай)

8 ноября 2017 · программирование · сортировки
Оставить комментарий (отменить)