Algorithm - Sorting (Selection Sorting) 選擇排序法

想法:

類似於 Bubble Sort

差別在於

Bubble Sort 是"尚未比較完畢的搜尋區內"每個節點鄰居做比較，條件成立就交換

Selection Sort 是"尚未比較完畢的搜尋區內"第一個節點與其後每個節點比較，條件成立就交換

因此每個回合會有一個點被定下來(可以是最大值也可以是最小值)

Code:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void swap(int *a, int *b);

void printarray(int size, int *data);

void generate_random_array(int size, int *data);

void bubblesort(int size, int *data);

void selectionsort(int size, int *data);

void swap(int *a, int *b){

    int tmp = *a;

    *a = *b;

    *b = tmp;

}

void printarray(int size, int *data){

    printf("data: ");

    for(int i = 0; i < size; i++){

        printf("%d,", data[i]);

    }

    printf("\n");

}

void generate_random_array(int size, int *data){

    srand(time(NULL));

    for(int i = 0; i < size; i++){

        data[i] = rand()%1000;

    }    

}

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include "Sort.h"

void selectionsort(int size, int *data){

    int i, j;

    for(i = 0; i < size; i++){

        for(j = i+1; j < size; j++){

            if(data[i] > data[j]){

                swap(&data[i], &data[j]);

            }

        }

        printarray(size, data);

    }

}

void main(){

    int size = 10;

    int *data = (int*)malloc(sizeof(int) * size);

    //generate random array

    generate_random_array(size, data);

    printf("original:\n");

    printarray(size, data);

    //sorting

    printf("sorting:\n");

    selectionsort(size, data);

    //result

    printf("result:\n");

    printarray(size, data);

}

複雜度:

時間複雜度: O(n^2) 雙重迴圈

空間複雜度: O(1) 不用額外的空間