# 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

{% embed url="<http://cathyatseneca.github.io/DSAnim/web/bubble.html>" %}

### C/C++ Implementation

```cpp
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

```cpp
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.

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

The inner for loop is more complicated:

```cpp
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:&#x20;

```cpp
j<size-1-i; j++
```

&#x20;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](https://catherine-leung.gitbook.io/data-strutures-and-algorithms/untitled#series) 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&#x20;

$$\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)$$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://catherine-leung.gitbook.io/data-strutures-and-algorithms/sorting/simple-sorts/the-simple-sorts.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.