C Program For Bubble Sort In Ascending Order

In this article, you will learn how to implement the Bubble Sort algorithm in C to arrange elements in ascending order, understanding its mechanism and practical application.

Problem Statement

Efficiently organizing data is a fundamental task in computer science. One common requirement is to sort a collection of elements, such as numbers in an array, into a specific order. Without an effective sorting algorithm, retrieving or processing ordered data becomes cumbersome and slow, especially with large datasets. The challenge is to devise a systematic way to reorder an array of unsorted numbers so that they appear in increasing sequence.

Example

Consider an unsorted array of integers: {64, 34, 25, 12, 22, 11, 90}. After applying the Bubble Sort algorithm in ascending order, the array should become: {11, 12, 22, 25, 34, 64, 90}.

Background & Knowledge Prerequisites

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

• C Programming Basics: Familiarity with variables, data types, and basic input/output.
• Arrays: How to declare, initialize, and access elements in an array.
• Loops: Knowledge of for loops for iteration.
• Conditional Statements: Understanding if statements for comparison.
• Functions: Basic concept of defining and calling functions.

Use Cases or Case Studies

Sorting algorithms like Bubble Sort, despite their simplicity, are foundational and serve various purposes:

• Educational Tool: Often used as a primary example to introduce sorting concepts due to its straightforward logic.
• Small Datasets: For very small arrays (e.g., fewer than 10-20 elements), its simplicity might outweigh the performance cost of more complex algorithms.
• Nearly Sorted Data: If an array is already mostly sorted, Bubble Sort can perform efficiently with a minor optimization (checking if any swaps occurred in a pass).
• Interactive Visualizations: Its step-by-step process of element "bubbling" makes it excellent for demonstrating sorting visually.
• Ranking and Ordering: Simple scenarios where items need to be displayed in a ranked order (e.g., highest scores, lowest prices).

Solution Approaches

Bubble Sort is a comparison-based sorting algorithm that 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.

Approach 1: Standard Bubble Sort for Ascending Order

This approach implements the classic Bubble Sort algorithm. It uses nested loops to iterate through the array, comparing each adjacent pair of elements. If the element on the left is greater than the element on the right, they are swapped to place the larger element further down the list. This continues until the largest element "bubbles" to its correct position at the end of the array, then the process repeats for the remaining unsorted part.

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

// Function to perform bubble sort
void bubbleSort(int arr[], int n) {
    int i, j;
    // Outer loop for passes
    for (i = 0; i < n - 1; i++) {
        // Inner loop for comparisons and swaps
        for (j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements
            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;
            }
        }
    }
}

// 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: Initialize 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 bubble sort function
    bubbleSort(arr, n);

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

    return 0;
}

Run

Sample Output:

Original array: 64 34 25 12 22 11 90 
Sorted array (ascending): 11 12 22 25 34 64 90

Stepwise Explanation:

1. bubbleSort(int arr[], int n) function:

• 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. We need n-1 passes because after n-1 passes, the largest n-1 elements are in their correct places, meaning the smallest element is also in its correct place.
• Inner Loop (for (j = 0; j < n - i - 1; j++)): This loop iterates through the unsorted portion of the array.
• n - i - 1: With each pass i of the outer loop, the largest i elements are already sorted and are at the end of the array. Therefore, the inner loop only needs to compare elements up to n - i - 1.
• Comparison (if (arr[j] > arr[j+1])): It compares adjacent elements arr[j] and arr[j+1].
• Swap: If arr[j] (left element) is greater than arr[j+1] (right element), they are in the wrong order for ascending sort. A temporary variable temp is used to swap their positions.

1. printArray(int arr[], int size) function: A utility function to display the contents of the array.
2. main() function:

• An example 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 straightforward sorting algorithm that is easy to understand and implement. Its mechanism of repeatedly comparing and swapping adjacent elements until the list is sorted makes it a good starting point for learning about sorting algorithms. While it is simple, its performance (O(n^2) time complexity) makes it less efficient for large datasets compared to more advanced algorithms.

Summary

• Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
• It is named "Bubble Sort" because larger elements "bubble" to the end of the list with each pass.
• The algorithm uses nested loops: an outer loop for passes and an inner loop for comparisons and swaps.
• In each pass, the largest unsorted element moves to its correct position.
• Despite its simplicity, it is not efficient for large datasets due to its quadratic time complexity (O(n^2)).
• It is particularly useful as an educational tool and for sorting very small or nearly sorted arrays.