How to do Bubble Sort in C Program?

In the field of computer science, sorting algorithms play a crucial role in organizing data. In this blog, we will cover bubble sorts’s working, and practical implementation, along with complexities followed by advantages and disadvantages.

Table of Contents:

• Overview of Sorting
• What is Bubble Sort in C?
• How Does Bubble Sort Work?
• Implementation of Bubble Sort in C
• Complexities of Bubble Sort
• Advantages and Disadvantages of Bubble Sort
• Wrap-up
• FAQs

Explore the world of Data Structures and Algorithms with this captivating YouTube video—your gateway to a comprehensive learning experience!

Overview of Sorting

Before stepping into what bubble sorting is, let us first understand Sorting.

Sorting in C refers to the process of arranging elements in a specific order within an array or other data structure. The primary goal of sorting is to make it easier to search for specific elements, perform efficient data retrieval, or facilitate other operations that benefit from ordered data. C provides various sorting algorithms, each with its own advantages and disadvantages, such as bubble sort, insertion sort, selection sort, merge sort and quicksort. 

What is Bubble Sort in C?

Bubble sort is an in-place comparison sorting algorithm that sequentially compares pairs of adjacent elements in an array and swaps their positions if they are not in the desired order. The algorithm performs multiple passes through the array until it is sorted.

On each pass, bubble sort compares each element to the element next to it, checking if they are ordered correctly with respect to each other. If two adjacent elements are not in the intended order, their positions are swapped. This process is repeated down the entire array on each pass. Elements that get sorted early in the process ‘bubble up’ to the correct positions, like bubbles rising up in the water.

The algorithm repeats this process of internal ‘bubbling’ by comparing and potentially swapping pairs of elements on each pass through the array until a complete pass occurs with no swaps. At that point, the array is fully sorted and the algorithm stops. Overall efficiency depends on the number of elements and if the array is partially sorted, but performance degrades quadratically in the worst case.

How Does Bubble Sort Work?

Bubble sort is like organizing a line of people by repeatedly switching places with the person next to you if they are not in the correct order. Let’s break it down step by step with a simple picture to help you understand.

Let’s consider the Input Array: [7, 8, 3, 1, 2]

1. First Round of Comparison

Compare the current element with the next one. If they are in the wrong order, swap them.

After First Pass: [7, 3, 1, 2, 8]

2. Second Round of Comparison

Move to the next pair of elements and repeat the comparison and swapping process.

After Second Pass: [3, 1, 2, 7, 8]

3. Third Round of Comparison

Repeat this process for the entire array until no more swaps are needed, indicating that the array is sorted.

After Third Pass: [1, 2, 3, 7, 8]

4. Fourth Round of Comparison

As there are a total of 5 elements in the array, the loop will iterate until n-1, i.e., till 4. However, since the array is already sorted after the third pass, no more swaps are needed in the fourth round.

After Fourth Pass: [1, 2, 3, 7, 8]

Implementation of Bubble Sort in C

Here’s a practical implementation of bubble sort in C programming:

#include <stdio.h>
// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Last i elements are already sorted, so no need to check them
        for (int j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap if they are in the wrong order
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

int main() {
    int arr[] = {7, 8, 3, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Print the original array
    printf("Input Array: [");
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) {
            printf(", ");
        }
    }
    printf("]\n");

    // Perform bubble sort
    bubbleSort(arr, n);

    // Print the sorted array
    printf("Sorted Array: [");
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) {
            printf(", ");
        }
    }
    printf("]\n");

    return 0;

}

Output:

Input Array: [7, 8, 3, 1, 2]

Sorted Array: [1, 2, 3, 7, 8]

Complexities of Bubble Sort

Complexities in programming refer to the analysis of the time and space efficiency of algorithms, providing insights into how their performance scales with input size.

The time and space complexities of the Bubble Sort algorithm are as follows:

Time Complexity: Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of the input.

• Worst Case: O(n^2) – This happens when every element in the input array needs to be switched during each run because it is in reverse order.
• Best Case: O(n) – This happens when there are no swaps required in any pass and the input array is already sorted. Still, the array must be scanned by the algorithm.
• Average Case: O(n^2) – Because bubble sort relies on comparisons and nested loops, it operates at a quadratic pace on average.

Space Complexity: Space complexity refers to the amount of memory space required by an algorithm in relation to its input size, describing how the space usage grows as the input size increases.

• Bubble Sort doesn’t require extra memory for auxiliary data structures because it is an in-place sorting method. As a result, regardless of the input size, its space complexity is O(1), showing constant space utilization.

Advantages and Disadvantages of Bubble Sort

Bubble Sort, a simple sorting algorithm, comes with its own set of advantages and disadvantages. Here are the following:

Advantages:

• Simple to understand and implement
• In-place sorting algorithm, requiring no additional memory
• Efficient for small datasets

Disadvantages:

• Inefficient for large datasets due to O(n^2) time complexity
• Makes many unnecessary comparisons even after the array is partially sorted
• Performs poorly with already sorted data

Wrap-Up

In a business context, Bubble Sort in C serves as a foundational learning tool for understanding sorting algorithms. It’s conceptually straightforward and valuable for educational purposes. However, its efficiency limitations with larger datasets make it less suitable for practical business applications. Future prospects lie in adopting more advanced sorting algorithms like quicksort or merge sort, which offer enhanced performance. When considering sorting algorithms for real-world scenarios, it’s essential to weigh the merits of Bubble Sort against the trade-offs involved.

FAQs