Selection sort

演算法類型

貪婪演算法, 排序演算法

演算法目的

藉由比較key value來將資料做排序

演算法描述

selection sort的精神是將資料切成兩部份，一部份爲已排序另一部份則是尚未排序，並且每次於尚未排序的資料堆中找出key value最小的資料放入已排序資料堆中的最後一個位置。舉例來說，有個數列如下:

現在此數列所有的數字都在未排序的資料堆裡，我們可以由左至右對數列做一次掃描，找出最小的數字1，並且將它與數列的第一個數字3做交換，這樣我們就可以把1歸納在已排序的資料堆裡，如下圖:

接著繼續從剩下未排序的資料堆裡，找出最小的數字3，並且將它與未排序資料堆的第一個數字5做交換，這樣就可以讓3被歸納在已排序的資料堆裡，如下圖:

再繼續從剩下未排序的資料堆裡，找出最小的數字4，並且將它與未排序資料堆的第一個數字9做交換，這樣就可以讓4被歸納在已排序的資料堆裡，如下圖:

依此類推，不斷地重複這些步驟就可以把全部的資料都排序好了。

效率分析

設總資料量爲n, 分析單位爲比較次數

第一次掃描找到最小值的比較次數: n - 1次
第二次掃描找到最小值的比較次數: n - 2次
第三次掃描找到最小值的比較次數: n - 3次

 ...

第n次掃描找到最小值的比較次數: 0次

總共比較次數: (0 + n - 1) * n / 2 = (n ^ 2 - n) / 2
故此演算法屬於O(n ^ 2)

程式實作

C

#include <stdio.h>

void selSort(int *, int);

int main() {
    int arr[8] = {3, 5, 9, 10, 8, 1, 12, 4};
    int dataNum = 8;
    int i;

    printf("before sorting: ");
    for (i=0; i<dataNum; i++)
        printf("%d ", arr[i]);
    printf("\n");
    selSort(arr, dataNum);
    printf("after sorting: ");
    for (i=0; i<dataNum; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

void selSort(int *arr, int dataNum) {
    int i, j;

    for (i=0; i<dataNum; i++) {
        int smallestIndex = i;

        for (j=i+1; j<dataNum; j++) {
            if (arr[smallestIndex] > arr[j])
                smallestIndex = j;
        }
        if (smallestIndex != i) {
            int temp = arr[smallestIndex];

            arr[smallestIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

Java

public class SelSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 9, 10, 8, 1, 12, 4};

        System.out.print("before sorting: ");
        for (int num: arr)
            System.out.printf("%d ", num);
        System.out.println();
        selSort(arr);
        System.out.print("after sorting: ");
        for (int num: arr)
            System.out.printf("%d ", num);
        System.out.println();
    }

    private static void selSort(int[] arr) {
        for (int i=0; i<arr.length; i++) {
            int smallestIndex = i;

            for (int j=i+1; j<arr.length; j++) {
                if (arr[smallestIndex] > arr[j])
                    smallestIndex = j;
            }
            if (smallestIndex != i) {
                int temp = arr[smallestIndex];

                arr[smallestIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

Python

def selSort(arr):
    for i in range(len(arr)):
        smallestIndex = i

        for j in range(i + 1, len(arr)):
            if arr[smallestIndex] > arr[j]:
                smallestIndex = j
        if smallestIndex != i:
            temp = arr[smallestIndex]
            arr[smallestIndex] = arr[i]
            arr[i] = temp

arr = [3, 5, 9, 10, 8, 1, 12, 4]
print "before sorting:",
for num in arr:
    print num,
print ""
selSort(arr)
print "after sorting:",
for num in arr:
    print num,
print ""