Bubble Sort

How to Use Bubble Sort in C Programming?

Bubble sort in C is a simple sorting algorithm that sorts the elements in ascending and descending order. It repeatedly compares the adjacent elements and swaps them if they are in the wrong order.

Example to understand Bubble Sort in C,

Suppose there is an array that contains ” 5 1 4 2 8″. If you want to sort this array in ascending order (lowest number to the greatest number), you need to take the following steps,

First Pass:

( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Here, the 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), the 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 )

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 )

 

Following is the implementation of Bubble Sort in C.

 

#include <stdio.h>

#define ARRAY_SIZE(x) sizeof(x)/sizeof(x[0])

//Function to swap element
void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}



//Function to sort the array
void BubbleSort(int *arr, int n)
{
    int i = 0, j = 0;

    for (i = 0; i < n-1; i++)
    {
        for (j = 0; j < n-i-1; j++)
        {
            if (arr[j] > arr[j+1])
            {
                Swap(&arr[j], &arr[j+1]);
            }
        }
    }
}


int main()
{
    int i = 0;

    //Array
    int arr[] = {6,5,3,1,8,7,2,4};

    //Get array size
    int n = ARRAY_SIZE(arr);

    //Function to sort array in ascending order
    BubbleSort(arr, n);

    printf("Array in ascending order: \n");

    //Print array
    for (i=0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

 

 

Output:  Array in ascending order: 1 2 3 4 5 6 7 8

Bubble Sort In C

 

 

Optimized Implementation of bubble sort:

The above-implemented code for bubble sort always runs O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if there is no swapping occur in the inner loop.

 

#include <stdio.h>

#define ARRAY_SIZE(x) sizeof(x)/sizeof(x[0])

//Function to swap element
void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

//Function to sort the array
void BubbleSort(int *arr, int n)
{
    int i = 0, j = 0;

    int  swapflag = 0;

    for (i = 0; i < n-1; i++)
    {
        swapflag = 0;

        for (j = 0; j < n-i-1; j++)
        {
            if (arr[j] > arr[j+1])
            {
                Swap(&arr[j], &arr[j+1]);
                swapflag = 1;
            }
        }

        //If inner loop not executed, break the loop
        if (swapflag == 0)
            break;
    }
}


int main()
{
    int i = 0;

    //Array
    int arr[] = {6,5,3,1,8,7,2,4};

    //Get array size
    int n = ARRAY_SIZE(arr);

    //Function to sort array in ascending order
    BubbleSort(arr, n);

    printf("Array in ascending order: \n");

    //Print array
    for (i=0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

 

Output:  Array in ascending order: 1 2 3 4 5 6 7 8

 

Important characteristics of Bubble Sort:

  • The best time complexity for Bubble Sort is O(n).
  • The average and worst time complexity is O(n²).
  • The space complexity for Bubble Sort is O(1).

 

Recommended Post