#include<stdio.h>

// 交換變量
inline void swap(int& a, int& b)
{
    a ^= b ^= a ^= b;
}

// 選擇排序（每次都在隊列中找出一個最值，然後將其置於隊列左側，並對剩下的元素重複此操作）
void sort1(int* arr, int sum)
{
    for (int i = 0; i < sum; i++)        // 每次循環確定第 i + 1 小的那個數
    {
        for (int j = i; j < sum; j++)    // 在 arr[i~n-1] 中搜尋最小的數
        {
            if (arr[j] < arr[i])        // 在 arr[i~n-1] 中一旦找到比 arr[i] 更小的數，就放到 arr[i] 中來（調換位置）
                swap(arr[i], arr[j]);
        }
    }
}

// 冒泡排序（按順序對隊列進行鄰位兩元素比較，每次比較若不合順序則左右調換，將在隊列右側產生一個最值，然後對剩餘元素重複此操作）
void sort2(int* arr, int sum)
{
    for (int i = 0; i < sum; i++)                    // 需要確定 sum 個元素的順序，即需要隊伍元素冒泡 sum 次
    {
        for (int j = 0; j + 1 < sum - 1 - i; j++)    // 隊伍的末尾已經有 i 個冒泡完畢的元素無需比較
        {
            if (arr[j] > arr[j + 1])                // 和選擇排序不同，冒泡排序是不合要求就調換，選擇排序是符合要求才調換
                swap(arr[j], arr[j + 1]);
        }
    }
}

// 打印數組
void print_arr(int* arr, int sum)
{
    for (int i = 0; i < sum; i++)
    {
        printf("%d", arr[i]);
        if (i != sum - 1)
            printf(", ");
    }
    printf("\n");
}

int main()
{
    const int sum = 7;
    int arr1[sum] = { 12, 5, 9, 9, 0, -1, 99 };
    int arr2[sum] = { 12, 5, 9, 9, 0, -1, 99 };

    printf("選擇排序：\n");
    print_arr(arr1, sum);
    sort1(arr1, sum);
    print_arr(arr1, sum);
    
    printf("冒泡排序：\n");
    print_arr(arr2, sum);
    sort2(arr2, sum);
    print_arr(arr2, sum);

    return 0;
}