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

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком.
Алгоритм концептуально простой, не требует вложенных циклов. Время работы  O(n²). На практике алгоритм может работать так же быстро, как и сортировка вставками.
Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.

Пример:

int* GnomeSort(int* Array, int SizeArray)
{
    int i=1;
    int j=2;
    int tmp;

    while(i<SizeArray)
    {
        if(Array[i]<Array[i-1])
        {
            i=j;
            j+=1;
        }
        else
        {
            tmp=Array[i-1];
            Array[i-1]=Array[i];
            Array[i]=tmp;
            i=i-1;
            if(0==i)
            {
                i=j;
                j=j+1;
            }
        }
    }
    return Array;
}

---

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