selection_sort.cpp

// selection_sort.cpp
// -----------------------------------------------------------------
// Selection Sort（選擇排序）
//
// 原理：每一輪從「未排序區」挑出最小元素，放到未排序區的最前端。
//       前 i 個元素永遠是整體最小的 i 個且已排好。
//
// 時間複雜度：最好 / 平均 / 最壞 都是 O(n^2)（比較次數固定）
// 空間複雜度：O(1)
// 穩定性：不穩定（遠距離交換可能打亂相等元素次序）
// 特點：交換次數最多 n-1 次——寫入成本高（如 EEPROM）時有優勢。
//
// Compile: g++ -std=c++17 -O2 -Wall -o selection_sort selection_sort.cpp
// -----------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void selectionSort(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) swap(a[i], a[minIdx]);
    }
}

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 = {
        {64, 25, 12, 22, 11},
        {5, 2, 9, 1, 5, 6},
        {1, 2, 3},
        {3, 2, 1},
        {42},
        {},
    };
    for (auto& t : tests) {
        printVec("before: ", t);
        selectionSort(t);
        printVec("after : ", t);
        cout << "sorted : " << boolalpha
             << is_sorted(t.begin(), t.end()) << "\n\n";
    }
    return 0;
}