Data Structures and Algorithms - Bubble Sort - Day 3 (Updated 12th August)

What is bubble sort

Bubble sort is and algorithm to sort an array. Here we compare the adjasent elements and swap them if the first element is greater than the second element. By default we sort in ascending order. The logic changes if we want a reverse order sort.

In bubble sort, after each loop through the array the highest element gets to/bubbles up to the end of the array. This is why this sort is known as bubble sort.

We repeat the process of swap until all the elements are bubbled up to their right position.

Example

Let’s consider the following array -

5 4 3 9 7

The size of the array a.k.a n = 5

We take two variables i and j for the outer and inner loop respectively.

As after each loop the last element is in its supposed position in the next loop we go upto the element previous to the last element.

Now a psudocode for the loops will be - W

i initialized to n-1 and decremented by 1 up to 0:
    j initialized to 0 and incremented by 1 up to i - 1:
        if the elemnet at index j of the array is greater than the element at index j+1 of array:
            perform swap so element at index j+1 becomes the element at index j and vice versa 

so now

i = 4

for j=0 we compare array’s 0th and 1st elements - in this case 5 and 4

Now as 5 > 4 we perform a swap and now the array looks like -

4 5 3 9 7

Now j becomes 1 so we are comparing 1st and 2nd index i.e. 5 and 3

Now as 5 > 3 we will perform another swap and the array will look like -

4 3 5 9 7

j = 2 now and we are comparing 2nd and 3rd index so 5 and 9

Now as 5 < 9 so there will be no swap

j = 3 now and we are comparing 3rd and 4th index so 9 and 7

Now as 9 < 7 so there will be a swap and the array will look like -

4 3 5 7 9

Now j = 4 which is not less than i(4) anymore so after the first outer loop the result is -

4 3 5 7 9

As you can see 9 is in position after this.

Now we perform the same thing but for i = 3

after that swap the array will be like -

3 4 5 7 9

as you can see the array is already sorted but we still loop through the array for i = 2 and i = 1

So the final sorted array is -

3 4 5 7 9

Code

#include<stdio.h>

int main() {
    int n;

    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter %d elements: ", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    int i, j, temp;

    for (i = n-1; i >=0; i--) {
        for (j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                // swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        //use this loop to see intermediate steps
        for (int k = 0; k < n; k++)
            printf("%d ", arr[k]);
        printf("\n");
    }

    printf("Sorted array: \n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

Time and space complexity (noted on 12th August)

Time and space complexity are important parameters to understand the efficiency of an algorithm.

For bubble sort we are going through n elements in the 1st loop; n-1 elements in the second loop and 1 element in the nth loop. So for an array with n elements bubble sort will have n + (n-1) + ... + 1 statements or swap comparisons executed. Which totals to n(n+1)/2 i.e. n^2/2 + n/2 loops. For time complexity we consider the highest power and get the complexity of O(n^2) as the time complexity of the algorithm.

Even if the array is sorted (best case) we will still need all the comparisons in this case.

So time complexity for -

Best case - O(n^2) Average case - O(n^2) Worst case (reverse order array) - O(n^2)

As we are not requiring any additional space it has a constant or O(1) complexity.