gnome_sort.cpp

// gnome_sort.cpp
// -----------------------------------------------------------------
// Gnome Sort（地精排序）
//
// 原理：類似插入排序但只用單一位置指標：
//       - 若目前元素 >= 前一個，前進一步。
//       - 否則交換並後退一步（像地精整理花盆）。
//
// 時間複雜度：最好 O(n)，平均 / 最壞 O(n^2)
// 空間複雜度：O(1)
// 穩定性：穩定
// 特點：程式碼極短，教學用途；效能與插入排序相近但交換較多。
//
// Compile: g++ -std=c++17 -O2 -Wall -o gnome_sort gnome_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void gnomeSort(vector<int>& a) {
    int n = (int)a.size();
    int i = 0;
    while (i < n) {
        if (i == 0 || a[i] >= a[i - 1]) {
            ++i;                    // 順序正確，前進
        } else {
            swap(a[i], a[i - 1]);   // 順序錯誤，交換並後退
            --i;
        }
    }
}

static void printVec(const string& tag, const vector<int>& a) {
    cout << tag;
    for (int x : a) cout << x << " ";
    cout << "\n";
}

int main() {
    vector<vector<int>> tests = {
        {34, 2, 10, -9},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3},
        {3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        gnomeSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}