Algorithm - Sorting (Bubble Sorting) 泡沫排序法

想法:

所有尚未被定位的資料會形成一個搜尋區

在搜尋區內，從最小的開始，一直跟鄰近的點比較，如果前面的點大於後面的點，則交換

所以在每個回合都會找到一個最大值

這個最大值就會被定下來並且不再加入比較(將最大值踢出搜尋區)

在下個回合一樣，在搜尋區內從最小的開始一直做比較

這個回合就會找到次大值(將次大值踢出搜尋區)

所以 bubble sorting 的概念就是在每個回合都會把最大值擠到最後面的 index 去

Code:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

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

void bubblesort(int size, int *data);

void printarray(int size, int *data);

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

    int tmp = *a;

    *a = *b;

    *b = tmp;

}

void bubblesort(int size, int *data){

    int i, j;

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

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

            if(data[j] > data[j+1]){

                swap(&data[j], &data[j+1]);

            }

        }

        printarray(size, data);

    }

}

void printarray(int size, int *data){

    printf("data: ");

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

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

    }

    printf("\n");

}

void main(){

    int size = 10;

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

    //generate random array

    srand(time(NULL));

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

        data[i] = rand()%1000;

    }

    printf("original:\n");

    printarray(size, data);

    //sorting

    printf("sorting:\n");

    bubblesort(size, data);

    //result

    printf("result:\n");

    printarray(size, data);

}

演示結果:

original: data: 75,456,61,668,97,55,465,25,612,63, sorting: data: 75,61,456,97,55,465,25,612,63,668, data: 61,75,97,55,456,25,465,63,612,668, data: 61,75,55,97,25,456,63,465,612,668, data: 61,55,75,25,97,63,456,465,612,668, data: 55,61,25,75,63,97,456,465,612,668, data: 55,25,61,63,75,97,456,465,612,668, data: 25,55,61,63,75,97,456,465,612,668, data: 25,55,61,63,75,97,456,465,612,668, data: 25,55,61,63,75,97,456,465,612,668, data: 25,55,61,63,75,97,456,465,612,668, result: data: 25,55,61,63,75,97,456,465,612,668,

複雜度:

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

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