Selection Sort (選擇排序法)

概念 - 教學影片

將數字們分成2類，未排序 和 已排序

一開始所有數字都是未排序

重複 N 次：

從未排序的數字中挑出最小的數字，放入已排序的最尾端。

依照上述

第1次可以挑到所有數字中第1小的數字 (最小的數字)

第2次可以挑到所有數字中第2小的數字

...

第N次可以挑到所有數字中第N小的數字 (最大的數字)

最後就由小到大排完了

實際操作

作法

1. 假設所有元素皆未排序
2. 從未排序的元素中，找出最小的元素
3. 把最小的元素與未排序數字中最左邊的值交換
4. 把未排序元素中最左邊的值，加入已排序序列
5. 重複步驟2-4 直到全部排完

備註 ： 黃色代表以排序，紅色代表當前最小值

Pseudo Code

const int N = 5;
int students[N] = {4,3,5,1,7};

void swap( int a , int b ){
    int temp = students[a];
    students[a]=students[b];
    students[b]=temp;
}

int main(){

    for ( int i = 0 ; i < N ; i++ ){
        int minPtr = i;
        for ( int j = i+1 ; j < N ; j++  ){
            if ( students[j] < students[minPtr] ){
                minPtr = j;   
            }
        }
        swap( i, minPtr );
    }

    for(int i =0;i<N;i++){
        cout<<students[i]<<" ";
    }

    return 0;
}