Bubble Sort in C | Bubble Sort Program in C

What is Bubble Sort?

Bubble Sort in C is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order. Bubble sort technique is used to sort an array of values in increasing or decreasing order.

Problem Description

Write a C program to perform the bubble sort.

Expected Input and Output

1. Average case (Unsorted array): When the input array has random distribution of numbers.

For example:

If the input array is {4, 6, 1, 2, 5, 3}      
the expected output array will have data as {1, 2, 3, 4, 5, 6}

2. Best case (Sorted Array): When the input array is already sorted, in that case we have to make minimum number of swaps.

For example:

If the input array has data as {-3, 31, 66}        
then the expected output array will have data as {-3, 31, 66}

3. Worst Case (Reverse sorted array): When the array is sorted in reverse manner, in that case we have to make maximum number of swaps.

For example:

If the input array has elements as {9, 8, 6, 3, 1}
then the output array will have data as {1, 3, 6, 8, 9}

Bubble Sort Algorithm

1. In Bubble sort algorithm we compare the first two elements of an array and swap them if required.
2. If we want to sort the elements of array in ascending order and if the first element is greater than second then, we need to swap the elements.
3. If the first element is smaller than second, we don’t need to swap the elements. This process go on until last and second last element is compared and swapped.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Pseudocode for Bubble Sort

bubble_sort(array):
  for i in range(len(array) - 1):
    for j in range(len(array) - i - 1):
      if array[j] > array[j + 1]:
        array[j], array[j + 1] = array[j + 1], array[j]

Bubble Sort Example:

If we have the array as {40,10,50,70,30}
and we apply bubble sort to sort the array,
then the resultant array after each iteration will be as follows:

               Original array: {40, 10, 50, 70, 30}

Array after first iteration          10  ->   40   ->   50   ->   30   ->   70
Array after second iteration         10  ->   40   ->   30   ->   50   ->   70
Array after third iteration          10  ->   30   ->   40   ->   50   ->   70
Array after fourth iteration         10  ->   30   ->   40   ->   50   ->   70
            
               Sorted array is  10  30  40  50  70

Problem Solution

There are many approaches to implement the bubble sort algorithm. Let’s take a detailed look at all the approaches to perform bubble sort in C.

Bubble Sort Program in C using Iterative Approach
Bubble Sort Program in C using Recursion
Sort N Numbers in Ascending Order using Bubble Sort

Method 1: Bubble Sort Program in C (Iterative Approach)

In the iterative approach to sort the array, we have to follow the given steps:

Take an element from the beginning of the array.
Compare it with its next element from the start to the end of the unsorted array.
If the first element is greater than the second element then swap them.
Repeat the above steps until the array does not sort.

Program/Source Code

Here is the source code of the C program to sort integers using Bubble Sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C Program to sort an array using Bubble Sort technique

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
void bubblesort(int arr[], int size)
```
```
{
```
```
    int i, j;
```
```
    for (i = 0;  i < size; i++)
```
```
    {
```
```
        for (j = 0; j < size - i; j++)
```
```
        {
```
```
            if (arr[j] > arr[j+1])
```

                swap(&arr[j], &arr[j+1]);

```
 
```
```
        }
```
```
    }
```
```
}
```
```
void swap(int *a, int *b)
```
```
{
```
```
    int temp;
```
```
    temp = *a;
```
```
    *a = *b;
```
```
    *b = temp;
```
```
}
```
```
int main()
```
```
{
```
```
    int array[100], i, size;
```

    printf("How many numbers you want to sort:  ");

```
    scanf("%d", &size);
```

    printf("\nEnter %d numbers : ", size);

```
    for (i = 0; i < size; i++)
```
```
        scanf("%d", &array[i]);
```
```
    bubblesort(array, size);
```
```
    printf("\nSorted array is ");
```
```
 
```
```
    for (i = 0; i < size; i++)
```
```
        printf(" %d ", array[i]);
```
```
    return 0;
```
```
}
```

Time Complexity: O(n²)
In the worst case, it should have to swap the n elements if the array is reverse sorted. The size of the list is n.

Space Complexity: O(1)
There is no need to use an extra space that depends on the size of the array. Hence the space completixty of bubble sort program is constant.

Runtime Test Cases

In this case, we are entering the numbers “345, 3, 20 35, 333” as input to sort them using bubble sort in ascending order.

$ gcc bubblesort.c -o bubblesort
$ ./bubblesort
 
How many numbers you want to sort: 5
 
Enter 5 numbers : 345 3 20 35 333
 
Sorted array is : 3 20 35 333 345

Method 2: (Recursive Bubble Sort)

To sort the array using the recursive approach we have to follow the given steps:

If the array length is less than 1 then stop the recursion.
On every traversing, place the largest element at the end of the array.
Repeat the above steps until the array does not sort.

Program/Source Code

Here is the source code of the C program to sort integers using Bubble Sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * Bubble Sort Program in C using recursion

```
 */
```
```
 
```
```
#include <stdio.h>
```
```
 
```
```
// function prototyping 
```
```
void bubble_sort(int*, int);
```
```
void print(int*, int);
```
```
 
```
```
int main()
```
```
{
```
```
    // initialize the integer array
```

    int arr[8] = {23, 3, 56, 78, 12, 1, 45, 21};

```
 
```
```
    // size of the array
```

    int size = sizeof(arr) / sizeof(arr[0]);

```
 
```
```
    // calling the function bubble sort
```
```
 
```

    printf("\nArray before sorting: \n");

```
    print(arr, size);
```
```
 
```
```
    bubble_sort(arr, size);
```

    printf("\n\nArray after sorting: \n");

```
    print(arr, size);
```
```
    return 0;
```
```
}
```
```
 
```

/* bubble_sort method takes the array and its size as parameter */

```
void bubble_sort(int arr[], int size)
```
```
{
```

    // base condition, when the array size is 1

```
    if(size <= 0)
```
```
    {
```
```
        return;
```
```
    }
```
```
 
```

    // place the largest element at the end of the unsorted size of the array

```
    for(int j=0; j<size-1; j++)
```
```
    {
```
```
        if(arr[j] > arr[j+1])
```
```
        {
```
```
            int temp = arr[j];
```
```
            arr[j] = arr[j+1];
```
```
            arr[j+1] = temp;
```
```
        }
```
```
    }
```
```
 
```
```
    // decrement the size of the array
```
```
    size -= 1;
```
```
 
```

    // recursive call to the bubble sort function

```
    bubble_sort(arr, size);
```
```
 
```
```
}
```
```
 
```

/* function to print the array of given size */

```
void print(int arr[], int size)
```
```
{
```
```
    for(int i=0; i<size; i++)
```
```
    {
```
```
        printf("%d ", arr[i]);
```
```
    }
```
```
}
```

Program Explanation

In the recursive approach, we have to call the function bubble sort until the array does not sort. In every function call, we have to place the largest element from the array at the unsorted array.

Time Complexity: O(n²)
Time taken to sort the array using bubble sort in the recursive approach is quadratic since we are placing the largest element on every iteration of the n-size array.

Space Complexity: O(n)
There are n functions calling stacks required to sort the array, where n is the size of the array.

Runtime Test Cases

In this case, we are entering the numbers “23 3 56 78 12 1 45 21” as input to sort them using bubble sort in ascending order.

Array before sorting: 
23 3 56 78 12 1 45 21 
 
Array after sorting: 
1 3 12 21 23 45 56 78

Method 3: Sort N Numbers in Ascending Order using Bubble Sort

In this method we sort the numbers in ascending order using bubble sort.

Program/Source Code

Here is source code of the C program to sort the numbers in ascending order using bubble sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C program to sort N numbers in ascending order using Bubble sort

 * and print both the given and the sorted array

```
 */
```
```
#include <stdio.h>
```
```
#define MAXSIZE 10
```
```
 
```
```
void main()
```
```
{
```
```
    int array[MAXSIZE];
```
```
    int i, j, num, temp;
```
```
 
```

    printf("Enter the value of num \n");

```
    scanf("%d", &num);
```

    printf("Enter the elements one by one \n");

```
    for (i = 0; i < num; i++)
```
```
    {
```
```
        scanf("%d", &array[i]);
```
```
    }
```
```
    printf("Input array is \n");
```
```
    for (i = 0; i < num; i++)
```
```
    {
```
```
        printf("%d\n", array[i]);
```
```
    }
```
```
    /*   Bubble sorting begins */
```
```
    for (i = 0; i < num; i++)
```
```
    {
```

        for (j = 0; j < (num - i - 1); j++)

```
        {
```

            if (array[j] > array[j + 1])

```
            {
```
```
                temp = array[j];
```

                array[j] = array[j + 1];

```
                array[j + 1] = temp;
```
```
            }
```
```
        }
```
```
    }
```
```
    printf("Sorted array is...\n");
```
```
    for (i = 0; i < num; i++)
```
```
    {
```
```
        printf("%d\n", array[i]);
```
```
    }
```
```
}
```

Runtime Test Cases

In this case, we are entering the numbers “23, 45, 67, 89, 12 and 34” as input to sort them using bubble sort in ascending order.

Enter the value of num
6
Enter the elements one by one
23
45
67
89
12
34
Input array is
23
45
67
89
12
34
Sorted array is...
12
23
34
45
67
89

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Generate Subsets with k Elements in each Subset

» Next - C program to Sort Integers using Quick Sort Technique

Related Posts:

Recommended Articles: