Bubble Sort Program in C

Bubble Sort Example

Let us say we have a list of Unicorns standing in a row in unsorted manner. Our task is to sort them in an ascending order using Bubble sort. 

Let us start our game to sort them: 

First Iteration 

Unicorn[0] will be compared with Unicorn[1] and if Unicorn[0] > Unicorn[1], then swapping will be performed. In our case, it is not true so the list remain as it is. 

As we move ahead towards the remaining Unicorns, we will apply the same analogy. 

Unicorn[1] will be compared with Unicorn[2]. Since it satisfies the condition, swapping will be performed. 

Unicorn[2] and Unicorn[3] will be compared now, and again it satisfies the condition, hence swapping will be performed. 

The first iteration ends over here. After each Iteration, the largest element will get placed in the right position. In the above example, Unicorn[3] is the tallest Unicorn and is placed at the right place. 

Let us proceed to the second pass:

We'll do the same thing we did in the first pass: Check adjacent elements and place them in the correct order, beginning with the first.

We already know that the last element is correctly placed, so we won't compare it to the second-last element.

So, our computation reduces to 0 - 2 indexes. 

Second Iteration

Unicorn[0] will be compared with Unicorn[1], it doesn’t satisfies the condition, so we will move ahead. 

Unicorn[1] will be compared with Unicorn[2], it satisfies the condition, swapping will be performed. 

Third Iteration

Unicorn[0] will be compared with Unicorn[1], it satisfies the condition so swapping will be performed and finally the list will be sorted. 

Let us now quickly see its algorithm. 

Working of Bubble Sort

Let's explore how the Bubble sort algorithm operates.

To grasp the inner workings of the bubble sort algorithm, let's consider an unordered array. Let's assume the array elements are -

1. First Iteration (Compare and Swap)

Let’s start this by comparing the first two elements: 

Here, 3<9, so it is already sorted. 

Here, 9>7, they need to be swapped as per the algorithm.

After swapping: 

Now, we’ll compare the next pair, here 9<11; no need for swapping.

For the last pair, because 11>1, swapping is performed.

After swapping:

2. Remaining Iteration

Second Iteration

The procedure is the same for the second iteration too. We’ll swap whenever we encounter left>right.

We encounter left>right here. Therefore swapping is required.

After swapping: 

Third Iteration

The procedure is the same for the third iteration too. We’ll swap whenever we encounter left>right.

This needs swapping.

After swapping: 

Fourth Iteration

Here only first pair is unsorted:

After swapping: 

Bubble Sort Algorithm in C

Below are the steps required to follow for the bubble sort program in c: 

1. Use two loops to iterate through the input array. 
2. The outer loop runs from i=0 to i=n-2.
3. The inner loop runs from j=0 to j=n-i-2;
4. For every j, compare arr[j] and arr[j+1]. If arr[j]>arr[j+1], then swap them or else move forward. 

Bubble Sort Implementation in C

// Bubble sort program in C
#include <stdio.h>

// perform the bubble sorting
void bubbleSort(int arr[], int size) {

  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
    
    // loop to perform comparison
    for (int i = 0; i < size - step - 1; ++i) {
     
       // compare two adjacent elements
      if (arr[i] > arr[i + 1]) {
       
         // swapping occurs if 
        // condition gets satisfied
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
}

int main() {
  int num[] = {2, 6, 4, -2, 8};
  
  // find the length of array 
  int size = sizeof(num) / sizeof(num[0]);
  
  bubbleSort(num, size);
 
  printf("Sorted Array in Ascending Order:\n");
  for (int i = 0; i < size; ++i) {
    printf("%d  ", num[i]);
  }
  printf("\n");
}

Output

Sorted Array in Ascending Order:
-2  2  4  6  8  

Optimized Bubble Sort Algorithm

In the typical bubble sort algorithm, the outer loop continues to execute even if we don't perform any swap operation in the inner loop. So, there will be no swapping if the elements are already sorted. 

To avoid these unnecessary comparisons, we can keep a flag set to false. If any swap is performed, it is set to true; otherwise, it remains false. 

Then at each iteration of the outer loop, we just need to check if the flag is false, we break the loop, or else we continue. 

In the next section, we will see the implementation of the bubble sort algorithm along with the space and time complexity. 

Optimized Bubble Sort Program in C

// Bubble sort program in C
#include <stdio.h>
// perform the bubble sorting
void bubbleSort(int arr[], int size) {
  
  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
      // 0 means false
         int isSwapped = 0;
   
     // loop to perform comparison
    for (int i = 0; i < size - step - 1; ++i) {
     
       // compare two adjacent elements
      if (arr[i] > arr[i + 1]) {
        
        // swapping occurs if 
        // condition gets satisfied
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;   
        
        // make it true
        isSwapped = 1;
      }
    }
    
    // no swapping means the array is sorted already
    if (!isSwapped) {
      break;
    }
  }
}
int main() {
  int num[] = {2, 6, 4, -2, 8};
 
   // find the length of array 
  int size = sizeof(num) / sizeof(num[0]);
  
  bubbleSort(num, size);
  
  printf("Sorted Array in Ascending Order:\n");
    for (int i = 0; i < size; ++i) {
    printf("%d  ", num[i]);
  }
  printf("\n");
}

Output

Sorted Array in Ascending Order:
-2  2  4  6  8  

Bubble Sort Time Complexity

The time complexity of the bubble sort algorithm is O(n²), where n is the number of elements present in the given array.

You can see that we use two nested loops for sorting. The inner loop can run up to n times, and the outer loop can also run up to n times in the worst case. Hence, the total number of comparisons will be O(n*n); thus, time complexity will be O(n*n) which is O(n²).

The best case occurs when the array is already sorted. So, the best case time complexity is O(n), as we need at least a single pass to know that no swapping has been performed. 

The worst case occurs when the array elements are sorted in reverse order, which implies that the algorithm will not finish before O(n²) operations. 

Bubble Sort Space Complexity

The space complexity of the bubble sort program in c algorithm is O(1). 

Since the algorithm uses only a constant amount of space for the loop variables and an extra variable to store the swapping status.

Moreover, bubble sort is an in-place sorting algorithm that manipulates the original array for sorting. 

Advantages of Bubble Sort Program in C

The following are some advantages of the Bubble sort algorithm:-

• Simplicity: Bubble Sort is one of the simplest sorting algorithms to understand and implement.
   
• Minimal Space Complexity: Bubble Sort operates in-place, meaning it doesn't require additional memory to store the sorted elements. It only needs a constant amount of extra memory for swapping elements.
   
• Useful for Nearly Sorted Data: Bubble Sort's performance improves when dealing with nearly sorted data since it requires fewer swaps to place elements in their correct positions.
   
• Stable Sorting: Bubble Sort maintains the relative order of equal elements, making it a stable sorting algorithm.

Disadvantages of Bubble Sort Program in C

The following are some disadvantages of the Bubble sort algorithm:-

• Inefficient for Large Datasets: Bubble Sort's time complexity of O(n^2) makes it highly inefficient for sorting large datasets, as the number of comparisons and swaps grows quadratically with the dataset size.
   
• Lack of Practicality: Due to its inefficiency, Bubble Sort is generally not suitable for real-world applications where sorting large or complex datasets quickly is crucial.
   
• Slow Sorting Speed: Even for moderately sized datasets, Bubble Sort can be significantly slower compared to more optimized sorting algorithms.
   
• No Early Termination: Bubble Sort always performs a fixed number of passes through the entire dataset, even if the data is already sorted. This results in unnecessary iterations.

Frequently Asked Questions

What is bubble sort program in C?

Bubble sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until the entire array is sorted in ascending or descending order.

What is bubble sort and write algorithm?

Bubble sort is a sorting algorithm that repeatedly traverses a list of elements, comparing adjacent elements and swapping them if they are in the wrong order. This algorithm has quadratic average case time complexity. 

What is the application of bubble sort?

Bubble Sort can be useful when dealing with very small datasets, where the overhead of more complex algorithms (such as quicksort or mergesort) might outweigh the benefits. It is also straightforward to implement.

Conclusion

In this article, we discussed the bubble sort program in c from scratch, starting with the introduction followed by the working of the algorithm with the help of an example. We also learned the optimized bubble sort algorithm's implementation and the time and space complexity analysis. 

We hope this blog has helped you enhance your knowledge of the bubble sort program in C. 

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

Happy Learning Ninjas!