Bubble Sort 泡沫排序法

1.Time complexity:

worst case: n*n
best cace  :n

2.我一個flag 判斷如果此回合沒有執行 swap則表示sort完畢

code如下:

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

int main (void)
{
    int k;
    int a[] = {88,7,87,9,80,100,800,300,400}; //You change the data what you want to sort
    int array_size = sizeof(a)/sizeof(int);


    printf("start bubble sort\n");
    BubbleSort(a,array_size);

    for(k = 0; k<array_size;k++) //print the result
        printf("a = %d\n",a[k]);


}

void BubbleSort(int data[],int array_size)
{
    int i,j,temp,q;
    int counta = 0;
    bool f;

    for(i=0; i< (array_size-1); i++) //execute the n-1 times
    {
        f = false;

        for(j=0;j<array_size-1-i;j++)
        {
            if(data[j]>data[j+1])
            {
                Swap(&data[j],&data[j+1]);
                f = true;

            }
            counta++;
        }
        /*
        printf("pass%d ",i);
        for(q=0;q<array_size;q++)
            printf("%d ",data[q]);
        printf("\n");
        */
        if(!f)break;
    }

}

void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


 1.每回合執行如下所示:
 

 2.但如果我拿掉if(!f) break 他會執行完n-1回合
 


這時候就知道演算法的強大了。