從原始資料序列中挑出最小(最大)的一項資料，並將他與目前正在處理的第 i 項交換

重複直到序列盡頭

#include<stdio.h>
#include<stdlib.h>

int find_min(int array[], int lidx, int ridx, int *comparePtr);
void selection_sort(int array[], int size);
void print_array(int array[], int size);

int main(void)
{
    int average_case[7] = {28, 13, 41, 69, 9, 24, 57};
    int best_case[7] = {9, 13, 24, 28, 41, 57, 69};
    int worst_case[7] = {69, 57, 41, 28, 24, 13, 9};

    printf("Average Case:\n");
    selection_sort(average_case, sizeof(average_case) / sizeof(average_case[0]));
    printf("\n\nBest Case:\n");
    selection_sort(best_case, sizeof(best_case) / sizeof(best_case[0]));
    printf("\n\nWorst Cast:\n");
    selection_sort(worst_case, sizeof(worst_case) / sizeof(worst_case[0]));
    printf("\n\n");
}


void selection_sort(int array[], int size)
{
    printf("%-8s", "initial");
    print_array(array, size);
    printf("%-8s%-2s%-10s\n", "compare", "|",  "move");
    printf("------------------------------------------------------------\n");

    int i, min_idx, compare, move;

    for(i = 0; i < size - 1; i++)
    {
        printf("%-s%-3d", "Pass ", i + 1);

        compare = 0;
        move = 0;

        min_idx = find_min(array, i, size - 1, &compare);

        int tmp = array[i];
        array[i] = array[min_idx];
        array[min_idx] = tmp;
        move++;

        print_array(array, size);
        printf("%-8d%-2s%-10d\n", compare, "|",  move);
    }
}


int find_min(int array[], int lidx, int ridx, int *comparePtr)
{
    int i, min_idx = lidx;
    for(i = lidx + 1; i <= ridx; i++)
    {
        (*comparePtr)++;
        if(array[i] < array[min_idx])
        {
            min_idx = i;
        }
    }

    return min_idx;
}


void print_array(int array[], int size)
{
    int i;
    for(i = 0; i < size; i++)
    {
        printf("| %-3d", array[i]);
    }

    printf(" | ");
}

這邊的做法沒有使用額外陣列空間，排序在 internal space 完成

空間複雜度為: O(1)

考慮下面這個 Case:

我們可以發現在 Pass 1 時 Selection 這個動作選到的最小值 3 在重複元素 28* 的右側

因此在交換時，原先在左側的 28 被換到了 28* 的右側

造成排序不穩定的特性

若要實現穩定的選擇排序演算法，可以透過額外空間來存放資料

1. 選出最小值後直接放進額外陣列空間
2. 將該最小值在原先陣列位置標記為無限大，表示已被處理過
3. 作法其實有點 merge sort 的概念