Bubble Sort

void bsort(int *array, int size)
{
    int i, j, swap_time;
 
    for (i = 0; i < size-1; i++) {
        swap_time = 0;
        for (j = 0; j < size - 1 - i; j++) {
            if (array[j] > array[j + 1])
                swap(array, j, j + 1);
            swap_time++;
        }
        if (!swap_time)
            break;
    }
}

Time Complexity

Best:
O(n) — when the array is already sorted, after we go through the array at the first time, there is no swapping happen, so finished.

Avg:
O(n2) — 1/2 + 2/2 + 3/2 + n-1/2 = n(n-1)/2/2 = O(n2)

Worst:
O(n2) — when the array is reversely sorted, 1 + 2 + 3 + … + n-1

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License