# 排序的穩定與不穩定

:::info
如果一個排序法，在兩個元素的排列順序相等時，若有辦法按原本在陣列中的順序排列，就說它屬於穩定排序（stable）；若做不到，則屬於不穩定排序（unstable）。
:::

對於一般整數而言，由於大小順序相同表示值完全相同，因此對調看不出影響；但規則一改，就可能有影響了。

例如按照先奇數再偶數的順序排列時，同是奇數的 $3$ 和 $7$，它們的排列順序相等，但值不相等。

例如按照字串長度排序時，字串 `abc` 和 `def` 長度相同，因此排列順序相等，但它們相異。

如果 $3, 7, 5, 2, 1, 4, 7$ 按照先奇數、後偶數的順序排序，由於所有奇數間的排列順序相同，所有偶數間的排列順序相同，結果應為 $3, 7, 5, 1, 7, 2, 4$。

有能力做到的，就是穩定排序；如果不能，就是不穩定排序。

## 哪些排序法穩定、哪些不穩定

:::info
目前提過的排序法，只有 Quick Sort 以及以它為核心的 intro sort 是不穩定的。
:::

quick sort 屬於不穩定排序，基於 quick sort 的 intro sort 也是，
因此 C++ 內建的 sort 也屬於不穩定排序。

:::warning
想想看，為什麼 quick sort 會屬於不穩定排序？
其它排序法又為何可以是穩定排序呢？
:::

一個簡單的測試方法是讓 sort 的比較函式永遠只回傳 false，
如此一來所有元素的順序會完全相等，只要看排序前後順序是否一致，
就知道是不是穩定排序。

:::warning
注意 intro sort 在 $n$ 夠小時會直接使用 insertion sort，
而 insertion sort 屬於穩定排序，因此如果 $n$ 不夠大，
可能測試不到 quick sort 導致誤以為 intro sort 是穩定排序。
:::

## 需要穩定排序時怎麼辦

一般有兩種方向：

:::info
- 改用穩定的排序法，例如 merge sort
- break tie 使排序規則上不可能相等
- sort by index (sort by pointer)
- 將 element 和 index 用 struct 打包起來一起排
:::

由於穩定和不穩定只在順序上相等時出現差異，如果元素間順序必定相異，那就沒有任何影響。

### 內建穩定排序 stable_sort

`<algorithm>` 提供另外一種選擇：stable_sort()，底層以 merge sort 實作，屬於穩定排序。

stable_sort(ary+i, ary+j+1);

用法和 sort() 基本相同。

### 打破平手 Break Tie

利用原本在序列中的 index 必定相異的特性，只要比較時有 index 參與就必定不會平手：

struct elem
{
    string val;
	int idx;
};

bool comp(const elem &p, const elem &q)
{
    // 第一優先條件：字串長度，由小到大
	if (p.val.size() != q.val.size())
	{
		return p.val.size() < q.val.size();
	}
    // 第二優先條件：元素原本的位置，由小到大
	return p.idx < q.idx;
}

### sort by index

sort by index 的概念是：保持序列原本順序不變，建立以 index 構成的新序列來排序。


如此不會破壞原資料的先後順序；原資料較大時，可以迴避大資料的搬動。在資料沒變動的前提下，能夠保留多種不同次序，不需每次對原資料重新排列。

const int N = 1005;
// 原資料
string str[N];
// index 序列
int idx[N];

// 對要排序的資料建立 index 序列
for (i=0; i<n; i++)
{
    idx[i] = i;
}
// 對 index 序列 sort
sort(idx, idx+n, comp);
// 按排好的 index 序列來取出原本資料
for (i=0; i<n; i++)
{
    j = idx[i];
    cout << str[j] << "\n";
}

bool comp(const int &a, const int &b)
{
    // 第一優先條件：字串長度，由小到大
    if (str[a].size() != str[b].size())
    {
        return str[a].size() < str[b].size();
    }
    // 第二優先條件：在原序列中的 index，由小到大
    return a < b;
}

## 歡樂練習時間

:::success
### Kattis sidewayssorting - Sideways Sorting
https://open.kattis.com/problems/sidewayssorting
:::

:::success
### Kattis sortofsorting - Sort of Sorting
https://open.kattis.com/problems/sortofsorting
:::

:::success
### VIP等級
你自製的網路遊戲 Ancient Plants Combat Saga（簡稱 APCS）上線後，
由於人氣爆發導致伺服器無法負荷，因此決定限制同時上線人數，
超過上限時需要排隊等候登入，而閒置太久的玩家則會被系統踹下線。

然而你不想讓身為衣食父母的課長們因排隊等待而棄坑，這將是筆大大的損失。
為此你建立了一套插隊系統，在遊戲內花過越多錢的，就能越早登入。
如果花一樣多錢，就遵守先來後到的規矩。

輸入先給一正整數 $n$ 代表有多少個人正在排隊登入，
接下來 $n$ 行每行有一串字串 $S_i$ 和一個非負整數 $M_i$，
$S_i$ 代表該帳號的 ID，只包含大小寫字母或數字，且長度不超過 $15$。
$M_i$ 為該帳號總計付過多少錢。

依照登入順序輸出每個帳號的 ID，一個帳號一行。

$1\le n\le 100000$
$0\le M_i\le 2,147,483,647$
不會有任兩個帳號 ID 相同。

#### 範例輸入

12
Marisa 100
Alice 2000
Yuugi 100
Sakuya 50000
Remilia 50000
Yuyuko 2000
Chiruno 9
Yuuka 0
Reimu 0
Furan 100
Suika 2000
Youmu 0

#### 範例輸出

Sakuya
Remilia
Alice
Yuyuko
Suika
Marisa
Yuugi
Furan
Chiruno
Yuuka
Reimu
Youmu

:::

{%hackmd @sa072686/__style %}

###### tags: `競程：二章`, `競程`