# 選擇排序法

你現在正在玩大老二。莊家把牌都發完了，你拿起手上的牌，用目光掃射了一遍，準備擬定戰略。運氣好一點，可以馬上把牌分成順子、葫蘆、鐵支等等，但若運氣差一點，只好先把牌由小到大排序，隨機應變。想一想，你會怎麼排？

在各種排序法中，**選擇排序**是最為直覺的一個方法。從手中的牌組，找出**最小的**那一張，放到**最左邊**；接著，撇開最左邊那張牌不看，一樣找出最小的，放在左邊數來第二張。以此類推，重複在未排序的牌中選擇最小的，由左至右排下去，就可以獲得次序由小到大的牌組。

問題來了，該如何找到「最小的」那張牌呢？
你一定覺得，這還用問嗎？掃射一遍就可以找到了。那我們換一個情境。全班總共有三、四十張考卷，請你找出最低分的那一張。你會怎麼做？

如果還沒想到，有請**東太平洋漁場時價分析師兼操盤手暨洋流講師：海龍王彼得**來給點提示！影片請看到0分40秒：

{%youtube nKUk6rCH1Us %}

彼得陸續說了一連串數字，請問，最便宜的海產是什麼？你是怎麼知道的？
沒意外的話，你不可能記下所有數字，而是一個、一個數字仔細聆聽，腦中只記一個數字：最小的那一個。選擇排序法的程式也是這樣的，他需要一個、一個數字去檢查，用一個變數`min`，記載每一回合的**最小值**。來看看動畫說明：

---
### 參考動畫
在第一回合的開始，先設`min`為最左邊的數字，一路往右找，若遇到更小的數字，他就是新的`min`。所有數字都檢查完後，接下來的操作跟我們想的不太一樣，並不是直接把最小值抽出來放到最左邊，而是將他跟最左邊的數字**交換位置（swap）**。為什麼呢？這跟數字儲存的方式有關。

我們知道，一串數字在程式中，通常會以**陣列（array）** 的形式儲存。在固定陣列空間（此例是a[6]，只能容納6個數字）的前提下，若要把一個數字放到最左邊，好幾個數字都要往右移動，徒增時間成本。將最小值跟最左邊的數字換位置，只有一次操作，就能確保陣列左邊是排序好的狀態。以此類推，你會發現每結束一回合，已排序好（sorted）的數字就多了一個，直到所有數字都排序完成。

BTW，有沒有同學注意到，怎麼數字交換完成，`min`還指著同一個地方呢？這是動畫的小bug。因為，在實作環節，我們會用`min`來記載最小值所在的**位置**，而非最小值本身。白話文的意思就是：最小值是**第幾個數字**。`min`成為一個**索引值**，可以用它取得陣列中的數字，進而交換位置。

如果看懂上面的說明，那麼恭喜你，可以進入程式實作的環節了！

---
### 參考流程圖（出處：資訊科技教科書，科友版）
(待改：最大改最小、右邊那一坨缺的流程)

---

### 解題思路
(待)

---

### 參考程式碼

#include <iostream>
using namespace std;
int main(){
	int n;
	cin >> n;
	int a[n];
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	/*	midx: 最小值的索引值	*/
	int midx, temp;
	/*	i: 第幾回合。    */
	for(int i=0; i<n-1; i++){
		/*    第幾回合就先設第幾個數字為最小值。    */
		midx = i;
		for(int j=i+1; j<n; j++){
			if (a[j] < a[midx])
				midx = j;
		}
		/*	將a[i]與a[midx]交換	*/
		temp = a[i];
		a[i] = a[midx];
		a[midx] = temp;

		cout << "round " << i+1 << ": ";
		for(int k=0; k<n; k++){
			//cout << a[k] << ((k==n-1)? "\n":" ");
			cout << a[k] << ((k==n-1)? "\n":(k==i)?"|":" ");
		}
	}

	cout << "sorted array: ";
	for(int i=0; i<n; i++){
		cout << a[i] << ((i==n-1)? "\n":" ");
	}
}

#### 輸入

6
5 2 4 6 1 3

#### 輸出

round 1: 1|2 4 6 5 3
round 2: 1 2|4 6 5 3
round 3: 1 2 3|6 5 4
round 4: 1 2 3 4|5 6
round 5: 1 2 3 4 5|6
sorted array: 1 2 3 4 5 6