Bubble Sort

Bubble Sort is the simplest sorting algorithm which compares all the adjacent elements one by one and sort them if they are in wrong order.

It is called Bubble Sort, because with each iteration the larger element in the list bubbles up towards the last (i.e in its final place).

Source: wikimedia

EXAMPLE OF BUBBLE SORT

Step-by-step example
Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

First Pass

( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass

( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

[Reference: wikipedia]

SIMPLE BUBBLE SORT

// C program for implementation of Bubble sort
#include <stdio.h>
 int main()
{
    int arr[] = {6, 3, 5, 2, 8, 10, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i, j,temp;
    //Bubble Sort starts
    for (i = 0; i < n-1; i++)      
    {
         for (j = 0; j < n-i-1; j++)
         {
              if (arr[j] > arr[j+1])
              {
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
           }
    }
    //Bubble Sort ends
    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

Output
Sorted array:
2 3 5 6 8 9 10

MODIFIED / OPTIMIZED BUBBLE SORT

The above function always runs O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if inner loop didn’t cause any swap.

// C program for Modified/Optimized Bubble sort
#include <stdio.h>
 int main()
{
    int arr[] = {6, 3, 5, 2, 8, 10, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i, j, temp, flag=0;
    //Modified Bubble Sort starts
    for (i = 0; i < n-1; i++)      
    {
         flag=0;
         for (j = 0; j < n-i-1; j++)
         {
              if (arr[j] > arr[j+1])
              {
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
                   flag=1;
               }
           }
           if(flag==0)
           { break;}
    }
    //Modified Bubble Sort ends
    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

Output
Sorted array:
2 3 5 6 8 9 10

COMPLEXITY ANALYSIS

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
Auxiliary Space Complexity: O(1). Only single extra memory space is required for temp variable for swapping.

EXAMPLE OF BUBBLE SORT

SIMPLE BUBBLE SORT

MODIFIED / OPTIMIZED BUBBLE SORT

COMPLEXITY ANALYSIS

Related Post