Home
Understanding and Implementing Bubble Sort in C: A Comprehensive Guide

Understanding and Implementing Bubble Sort in C: A Comprehensive Guide

January 16, 2025 Digital

Understanding and Implementing Bubble Sort in C: A Comprehensive Guide

Bubble sort is one of the simplest and most basic sorting algorithms used in programming. Despite its simplicity, it has its place in algorithm studies, particularly in teaching the principles of algorithm design and time complexity analysis. This article aims to provide a detailed understanding of the bubble sort algorithm along with its implementation in the C language.

Introduction to Bubble Sort

Bubble sort is a simple comparison-based sorting algorithm. It 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. The pass through the list is repeated until no swaps are needed, indicating that the list is sorted.

Algorithm Explanation

Basic Bubble Sort

The basic idea behind bubble sort is to iterate through the array, compare each pair of adjacent elements, and swap them if they are in the wrong order. This process is repeated until the entire array is sorted. Here's a simple implementation of bubble sort in C:

void bubbleSort(int array[], int size) {    for (int i  0; i  size - 1; i  ) {        for (int j  0; j  size - i - 1; j  ) {            if (array[j]  array[j   1]) {                // Swap array[j] and array[j 1]                int temp  array[j];                array[j]  array[j   1];                array[j   1]  temp;            }        }    }}

This function takes an array and its size as input and sorts the array in ascending order.

Example and Walkthrough

Consider an array arr[] {2, 10, 8, 7}. Here's how bubble sort would work:

First pass: The highest value (10) moves to the last position.

{2, 10, 8, 7} → {2, 8, 10, 7} (2 10, no swap) {2, 10, 8, 7} → {2, 8, 7, 10} (8 7, swap)

Second pass: The second-highest value (10) moves to the second last position.

{2, 8, 7, 10} → {2, 8, 7, 10} (2 8, no swap)

Third pass: The sorted order is achieved as no more swaps are needed.

Complete Program

C 
                #include stdio.h
void bubbleSort(int array[], int size) {
    for (int i  0; i  size - 1; i  ) {
        for (int j  0; j  size - i - 1; j  ) {
            if (array[j]  array[j   1]) {
                int temp  array[j];
                array[j]  array[j   1];
                array[j   1]  temp;
            }
        }
    }
}
void printArray(int arr[] , int size) {
    for (int i  0; i  size; i  ) {
        printf(%d , arr[i]);
    }
    printf(
);
}
int main() {
    int arr[]  {64, 34, 25, 12, 22, 11, 90};
    int n  sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: 
");
    printArray(arr, n);
    return 0;
}

Time Complexity and Auxiliary Space

Time Complexity

The worst-case and average time complexity of bubble sort is O(N^2), where N is the number of items being sorted. This is because in the worst case, every element needs to be compared and swapped with every other element.

Auxiliary Space

Bubble sort requires only a single additional memory space for temporary storage, which makes its auxiliary space complexity O(1).

Optimized Bubble Sort

While bubble sort is simple and easy to implement, it has a time complexity that makes it less suitable for large datasets. However, by adding a flag to detect if any swapping has occurred, we can optimize the algorithm. If no elements were swapped during a pass, then the array is already sorted, and there is no need to continue sorting.

void bubbleSort(int arr[], int n) {    int i, j;    bool swapped;    for (i  0; i  n - 1; i  ) {        swapped  false;        for (j  0; j  n - i - 1; j  ) {            if (arr[j]  arr[j   1]) {                // Swap arr[j] and arr[j 1]                int temp  arr[j];                arr[j]  arr[j   1];                arr[j   1]  temp;                swapped  true;            }        }        if (!swapped) break;    }}

This optimization reduces the number of passes through the array, making it potentially faster than the basic version for almost-sorted arrays.

Conclusion

Bubble sort, while simple, is a fundamental algorithm for understanding the principles of sorting. Its implementation and optimization provide insights into the trade-offs between simplicity and efficiency. For most real-world applications, more advanced sorting algorithms like QuickSort or MergeSort would be more appropriate, but bubble sort remains a valuable learning tool.

If you found this article helpful, please do not forget to upvote, follow, and share it with others. Thank you!

Related Posts