C Program For Bubble Sort Algorithm

This article explores the Bubble Sort algorithm, a fundamental sorting technique. In this article, you will learn how Bubble Sort works and how to implement it efficiently in the C programming language.

Problem Statement

Efficiently organizing data is a common requirement in computer science and programming. Sorting involves arranging elements of a list in a particular order, such as ascending or descending. The challenge lies in developing algorithms that can perform this reordering reliably and with acceptable performance, especially for larger datasets.

Example

Consider an unsorted list of numbers: [64, 34, 25, 12, 22, 11, 90]. After applying the Bubble Sort algorithm, the list will be sorted in ascending order as: [11, 12, 22, 25, 34, 64, 90].

Background & Knowledge Prerequisites

To understand and implement Bubble Sort in C, readers should have a basic understanding of:

• C Programming Basics: Variables, data types, operators.
• Arrays: How to declare, initialize, and access elements of an array.
• Loops: for loops for iteration.
• Conditional Statements: if statements for comparison.
• Functions: Defining and calling functions (though the core logic can be in main).

Use Cases or Case Studies

Sorting algorithms like Bubble Sort, despite their simplicity, have various applications:

• Educational Purposes: Bubble Sort is an excellent algorithm for beginners to learn about sorting due to its straightforward logic, making it a common subject in introductory programming courses.
• Small Datasets: For very small arrays (e.g., fewer than 10-20 elements), the overhead of more complex algorithms can sometimes outweigh the performance benefits, making Bubble Sort a viable, simple option.
• Near-Sorted Data: If a list is already nearly sorted, Bubble Sort can perform relatively well in its optimized version (with a swapped flag), as it quickly identifies that few passes are needed.
• Interactive Visualizations: Its step-by-step comparisons and swaps make it easy to visualize, often used in educational tools to demonstrate how sorting works.
• Component of Other Algorithms: Sometimes, sorting small internal chunks of data within a larger, more complex algorithm might use a simple method like Bubble Sort.

Solution Approaches

Implementing Bubble Sort in C

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, indicating that the list is sorted.

// Bubble Sort Algorithm
#include <stdio.h>

// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
    int i, j;
    // Outer loop for passes (n-1 passes)
    for (i = 0; i < n - 1; i++) {
        // Inner loop for comparisons in each pass
        for (j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap if they are in the wrong order
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\\n");
}

int main() {
    // Step 1: Define an unsorted array
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array
    printf("Original array: ");
    printArray(arr, n);

    // Step 3: Call the bubbleSort function
    bubbleSort(arr, n);

    // Step 4: Print the sorted array
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output:

Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90

Stepwise Explanation:

1. bubbleSort Function:

• It takes an integer array arr and its size n as input.
• Outer Loop (for (i = 0; i < n - 1; i++)): This loop controls the number of passes through the array. In each pass, at least one element "bubbles up" to its correct position. For an array of n elements, n-1 passes are sufficient.
• Inner Loop (for (j = 0; j < n - i - 1; j++)): This loop performs the comparisons and swaps within each pass.
• n - i - 1: With each pass i, the largest i elements are already at the end of the array (sorted). So, we don't need to compare elements beyond n - i - 1. This optimizes the inner loop's range.
• Comparison and Swap (if (arr[j] > arr[j + 1])): If the current element (arr[j]) is greater than the next element (arr[j + 1]), they are in the wrong order.
• Swap: A temporary variable temp is used to facilitate swapping the positions of arr[j] and arr[j + 1].

1. printArray Function: A helper function to display the contents of an array.
2. main Function:

• An example integer array arr is initialized.
• The size n of the array is calculated.
• The original array is printed.
• The bubbleSort function is called to sort the array.
• The sorted array is then printed.

Conclusion

Bubble Sort is a simple comparison-based sorting algorithm. While easy to understand and implement, its time complexity of O(n^2) in the worst and average cases makes it inefficient for large datasets. It remains a valuable tool for learning fundamental sorting concepts and for scenarios involving very small or nearly sorted arrays.

Summary

• Bubble Sort repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order.
• The process continues until no swaps are made in a pass, indicating the list is sorted.
• It has a time complexity of O(n^2), making it less suitable for large arrays.
• Despite its inefficiency for large data, it is excellent for educational purposes and sorting small or nearly sorted lists.
• The C implementation involves nested loops: an outer loop for passes and an inner loop for comparisons and potential swaps.