:::info
將資料由小到大或由大到小排列，常見排序演算法有氣泡排序、選擇排序、插入排序、合併排序與快速排序等，其中以合併排序與快速排序的演算法效率比較好，但程式也較複雜。
:::

# 氣泡排序法(BubbleSort)

:::warning
Bubble Sort 的方式是從陣列的最前面開始，一次比較陣列中兩兩相鄰的元素，然後根據大小將它們調換順序，大的移到後面：

1. 當我們比較過所有元素一次後，可以確保數值最大的元素在最後面
2. 接著扣掉陣列中的最後一個元素（因為已經確定它是最大的），接著重複上面的步驟進行兩兩比較
3. 重複上述動作，直到排序完畢。假設這個陣列有 6 個元素一共需重複這個動作 5 次
:::

:::success
1. 隨機產生一個陣列10個1~10000的整數元素
2. 以氣泡排序演算法將這10個元素由小到大排序
3. 輸出元素兩兩間以一個空白隔開
4. 每行最多輸出5個元素
:::

#include <iostream>
//取得自1970/1/1 12:00:00 開始至現在所經過的時間
#include <ctime>
//srand(), rand()
#include <cstdlib>
//sort()
#include <algorithm>

using namespace std;

const int SIZE = 10;
const int NUM_PER_LINE = 5;
int a[SIZE];
const int MAX_NUM = 10000;

// 1.產生SIZE個整數(1~10000)的陣列
void generateArray(int SIZE)
{
    //產生亂數種子(Bandom seed)
    //srand(time(NULL));
    srand((unsigned int)time(NULL));
    //產生10個 1~10000的數字存到a陣列中
    for(int i=0; i<SIZE; i++){
        //產生 1~10000的亂數整數
        a[i] = rand()%MAX_NUM + 1;

    }
}
// 2.顯示陣列資料
// 輸出元素兩兩間以一個空白隔開,最後一個元素和不能有空白
// 每行最多顯示 NUM_PER_LINE 個元素
void displayArray(int SIZE, int NUM_PER_LINE)
{
    /*解法1
    for(int i=0; i<SIZE; i++)
    {
        if(i==(SIZE-1))
            cout<<a[i]<<"\n";
        else
            cout<<a[i]<<" ";
    }
    cout<<"\n";

    //解法2
    cout<<a[0];
    for(int i=1; i<SIZE; i++)
        cout<<" "<<a[i];
    cout<<"\n";*/

    int counter=0;  //紀錄已經顯示的個數
    int firat = 1;  //紀錄是否為每行的第一個元素

    for(int i=0; i<SIZE; i++) //輸出SIZE個元素
    {
        if(firat) //是每行的第一個元素
        {
            firat=0; cout<<a[i];
        }
        else //不是每行的第一個元素
        {
            cout<<" "<<a[i];
        }
        //1.先將counter+1
        //2.counter 是否被NUM_PER_LINE整除
        //3.判斷條件是否成立
        if(!(++counter%NUM_PER_LINE))
        {
            cout<<"\n"; firat=1;
        }
    }
}

// 3.開始排序
void bubbleSort(int a[], int SIZE)
{
    for(int i=0; i<SIZE-1; i++)
    {
        for(int j=0; SIZE-1-i; j++)
        {
            if(a[j]>a[j+1])
            {
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

bool cmp(int p, int q){
    return p>q;
}
int main()
{
    // 1.產生SIZE個整數(1~10000)的陣列
    generateArray(SIZE);
    // 2.顯示陣列資料
    cout<<"Before sorting:\n";sort(a, a+SIZE);
    displayArray(SIZE, NUM_PER_LINE);
    // 3.開始排序
    bubbleSort(a, SIZE);
    // 4.顯示陣列資料
    cout<<"After ASC. sorted;\n";
    displayArray(SIZE, NUM_PER_LINE);

    cout<<"\n\nUsing sort Algorithm:\n";
    generateArray(SIZE);
    cout<<"Before DEC. sorting:\n";
    displayArray(SIZE, NUM_PER_LINE);

    //sort(a, a+SIZE);  //一定要加入algorithm標頭檔
    sort(a, a+SIZE, cmp);  //由大到小
    cout<<"After sorted:\n";
    displayArray(SIZE, NUM_PER_LINE);

    return 0;

}

# 多鍵值排序(Multi-Key Sorting)
:::warning
1.若同時間有多個鍵值需要比較，稱為多鍵值排序
2.程式也可以進行多鍵值排序，需要自訂結構（struct）
3.定義cmp 函式，最後使用STL 的sort 函式與cmp 函式進行多鍵值排序。
:::
:::success
請寫一個程式，隨機產生20個學生的國文、英文與數學成績
再依照國文、英文與數學排序，也就是若國文同分則比較英文，若英文同分則比較數學。
:::

#include <iostream>
#include <ctime>    //for time()
#include <cstdlib>  //for stand().rand()
#include <algorithm>//for sort()

#define NUMOFSTUDETS 20
#define MINSOORE    61
using namespace std;

//int a[NUMOFSTUDETS];  //這是錯的因為這樣寫只能儲存一個key

//定義學生分數的結構，包含國文、英文、數學3科分數
typedef struct _score{
    int chi;
    int eng;
    int math;
    //int chi,eng,math簡寫
}SCORE;

//宣告 儲存NUMOFSTUDENTS 的成績資料
SCORE a[NUMOFSTUDETS];

 //1.利用亂數產生 SIZE個 學生成績資料
 //隨機產生20個學生的 國文、英文與數學成績(61~100)
 void generateStudentData()
 {
    //取得 random seed
    srand(time(NULL));
    //產生size 個學生的 國文、英文與數學成績(61~100)
    for(int i=0; i<NUMOFSTUDETS; i++){
        a[i].chi = rand()% 40 + 61;
        a[i].eng = rand()% 40 + 61;
        a[i].math = rand()% 40 + 61;
    }

 }
//2.顯示陣列資料
void displayStudentData()
{
    for(int i=0; i<NUMOFSTUDETS; i++){
        cout<<"Chinese = " <<a[i].chi<<" "
            <<"English = " <<a[i].eng<<" "
            <<"Math = " <<a[i].math<<"\n";
    }
}

//3.自訂多key排序
//若國文同分級比較英文，若英文同分則比較數學
int cmp(SCORE p, SCORE q){
    //如果 國文分數相同且英文也相同，則比較數學
    if(p.chi==q.chi&& p.eng==q.eng) return p.math>p.math;
    //如果 國文相同，比較英文
    else if(p.chi==q.chi) return p.eng>q.eng;
    else return p.chi>q.chi;    //如果 沒有相同，比較國文
}
int main()
{
    //1.利用亂數產生 SIZE個 學生成績資料
    generateStudentData();

    //2.顯示亂數產生的學生原始資料
    cout<<"Original data:\n";
    displayStudentData();

    //3.根據排序需求進行排序
    sort(a, a+NUMOFSTUDETS, cmp);

    //4.顯示排序後資料
    cout<<"\n\nSorted data:\n";
    displayStudentData();
    return 0;
}