Гномья СортировкаGnome Sort

Единственный указатель i движется по массиву. Если i == 0 или a[i-1] ≤ a[i], пара в порядке — i увеличивается на 1 (шаг вперёд). Иначе пара нарушена — элементы меняются местами, и i уменьшается на 1 (шаг назад, чтобы проверить новую пару перед переставленным элементом). Алгоритм завершается, когда i достигает конца массива. Инвариант в точности как у insertion sort — префикс [0, i) в момент шага вперёд всегда отсортирован — но здесь это следует не из явного вложенного while, а из того, что каждый шаг назад "протаскивает" неуместный элемент ровно на одну позицию влево, точно так же, как внутренний цикл insertion sort, просто в других терминах.A single pointer i moves through the array. If i == 0 or a[i-1] ≤ a[i], the pair is in order — i increases by 1 (step forward). Otherwise the pair is violated — the elements are swapped, and i decreases by 1 (step back, to check the new pair in front of the swapped element). The algorithm finishes when i reaches the array's end. The invariant is exactly insertion sort's — the prefix [0, i) at the moment of a forward step is always sorted — but here it follows not from an explicit nested while but from each backward step "dragging" a misplaced element exactly one position left, the same as insertion sort's inner loop, just phrased differently.

void gnome_sort(std::vector<int>& a) {
    int i = 0;
    int n = (int)a.size();
    while (i < n) {
        if (i == 0 || a[i - 1] <= a[i]) {
            ++i;                          // пара в порядке — шаг вперёд// pair is fine — step forward
        } else {
            std::swap(a[i - 1], a[i]);
            --i;                          // пара нарушена — свап и шаг назад// pair violated — swap and step back
        }
    }
}

Указатель (жёлтая подсветка пары) движется вперёд или назад в зависимости от одного простого сравнения. Обратите внимание, как отсутствие вложенного цикла не меняет число операций — оно просто "размазано" по одному внешнему циклу.The pointer (yellow pair highlight) moves forward or backward based on one simple comparison. Notice how the absence of a nested loop doesn't change the operation count — it's just "spread out" over a single outer loop.

Каждый шаг назад в gnome sort соответствует ровно одной итерации внутреннего while в insertion sort (2.2.1.1) — оба сдвигают один "неуместный" элемент на одну позицию влево. Каждый шаг вперёд соответствует переходу insertion sort к следующему i во внешнем цикле. Поэтому число элементарных операций у обоих алгоритмов совпадает день в день: Θ(n²) в худшем случае (например, при массиве, отсортированном по убыванию), Θ(n) на уже отсортированном входе — та же адаптивность, что и у insertion sort, просто выраженная другим управлением потоком. Разница чисто синтаксическая, а не алгоритмическая.Every backward step in gnome sort corresponds to exactly one iteration of insertion sort's (2.2.1.1) inner while — both shift one "misplaced" element one position left. Every forward step corresponds to insertion sort's outer loop advancing to the next i. So both algorithms' operation counts match exactly: Θ(n²) worst case (e.g. a descending array), Θ(n) on an already-sorted input — the same adaptivity as insertion sort, just expressed with different control flow. The difference is purely syntactic, not algorithmic.