Bubble Sort

Introduction

Bubble sort is called bubble sort because the algorithm repeated bubbles the largest item within the list to the back.

Algorithm

1. start with first pair of numbers

2. compare them and if they are not correctly ordered, swap them

3. go through every pair in list doing the above 2 steps

4. repeat the above 3 steps n-1 times (ie go through entire array n-1 times) and you will sort the array

Animation

Data Structure Animations using Processing.js by cathyatseneca

C/C++ Implementation

void bubbleSort(int arr[],int size){
    int tmp;                          /*used for swapping*/
    int i;
    int j;
    for (i=0; i<size-1; i++) {
        for (j=0; j<size-1-i; j++){
            int next = j+1;
            if (arr[next] < arr[j]) {          /* compare the two neighbors */
                tmp = arr[j];                   /* swap a[j] and a[j+1]      */
                arr[j] = arr[next];
                arr[next] = tmp;
            }
        }
    }
}

Analysis

Let $n$ represent the size of the array Let $T(n)$ represent the number of operations needed to bubble sort the array.

We put in the operator counts as normals

void bubbleSort(int arr[],int size){
    int tmp;                                //1
    int i;                                  //1  
    int j;                                  //1
    for (i=0; i<size-1; i++) {              //1 + 3(n-1)
        for (j=0; j<size-1-i; j++){         //(n-1) + 4(n-1) + 4(n-2) + 4(n-3)...
                                            // + 4(1)
            int next = j+1;                 // 2(n-1) + 2(n-2) + ... + 2(1)
            if (arr[next] < arr[j]) {       // (n-1) + 2(n-2) +... + 2(1)
                tmp = arr[j];               // (n-1) + (n-2) + ... + 1
                arr[j] = arr[next];         // (n-1) + 2(n-2) + ... + 2(1)
                arr[next] = tmp;            // (n-1) + 2(n-2) + ... + 2(1)
            }
        }
    }
}

Now.. lets go through why these counts are what they are... this outer for loops runs n-1 times... so 1 op for initialization, n-1 for the other 3 operators.

    for (i=0; i<size-1; i++) {              //1 + 3(n-1)

The inner for loop is more complicated:

for (j=0; j<size-1-i; j++){         //(n-1) + 4(n-1) + 4(n-2) + 4(n-3)...
                                            // + 4(1)

j=0 is done once every time this loop runs. This inner loop is inside the outer loop which runs n-1 times, thus, j=0 runs exactly n-1 times.

For this part of the loop statement:

j<size-1-i; j++

there are 4 operators in total (<, -, - and ++). They run for each iteration of the inner loop. The number of iterations of each run of the innerloop though depends on the value of i. When i = 0, the inner loop runs n-1 times. when i = 1, it runs n-2 time, when i = 3, it runs n-3 times... etc. i goes up to n-2 at most. when i = n-2, the loop runs one time. Thus... if we were to add up every single iteration of the inner loop, we would need to add it all up. Thus, 4(n-1) + 4(n-2) + 4(n-3) + .... 4(1)

Similarly we count the operators inside the inner loop the same way...

Another way we can sum up the inner loop is at follows... if we count all the operations in the inner loop (we assume if is always true and count all ops inside the if statement) there are a total of 10 operators (4 operators in the j loop header, 6 within the body). Now, if we count how many iterations in total the inner loop runs in total (for each iteration of i) we can then simply multiply that by 10.

i	size-1-i (number of iterations of inner loop)
0	n-1 - 0 = n-1
1	n-1-1 = n-2
2	n-1-2 = n-3
3	n-1-3 = n-4
...	...
n-2	n-1-(n-2) = 1
Total:	(n-1) + (n-2) + (n-3) + .... + 1

Using this method, we establish that the expresion (n-1) + (n-2) + (n-3) + .... +1 represents the total number of iterations.

But ..

$(n-1) + (n-2) + (n-3) + .... +1 = \sum\limits_{i=1}^{n-1}{i}$

From the Appendix: Mathematics Review section, we find this formula for this series:

$\sum\limits_{i=1}^{N} {i} = \frac{N(N+1)}{2}​$

So, if we substitute n-1 for N, our expression for

$\sum\limits_{i=1}^{n-1}{i} = { (n-1) (n-1 +1) \over 2}$

Putting this all together:

\begin{align*}T(n) &= 10({ (n-1) (n-1 +1) \over 2}) + 3(n-1) + 4 \\ &= 5(n-1)(n) + 3n - 3 + 4 \\ &= 5n^2 - 5n + 3n +1 \\ &= 5n^2 -2n + 1 \end{align*}

The dominating term is $5n^2$ . Therefore:

$T(n)$is $O(n^2)$