C Program For Bubble Sort Using Array

Sorting data is a fundamental operation in computer science, essential for efficient data processing and retrieval. In this article, you will learn how to implement the Bubble Sort algorithm using arrays in C, understanding its mechanics and practical application.

Problem Statement

Imagine you have a collection of items, such as a list of numbers or names, that are arranged randomly. The problem is to efficiently organize these items into a specific order, typically ascending (smallest to largest) or descending (largest to smallest). Unsorted data can make searching, analyzing, or presenting information challenging and time-consuming.

Example

Consider an array of integers that needs to be sorted in ascending order:

Unsorted Array: [5, 1, 4, 2, 8]

After applying a sorting algorithm, the array should become:

Sorted Array: [1, 2, 4, 5, 8]

Background & Knowledge Prerequisites

To understand the C program for Bubble Sort, readers should be familiar with the following basic C programming concepts:

• Variables and Data Types: Understanding how to declare and use integer variables.
• Arrays: Knowledge of how to declare, initialize, and access elements within an array.
• Loops: Familiarity with for loops for iterating over arrays.
• Conditional Statements: Understanding if statements for comparing values.
• Functions: Basic understanding of main function and custom functions (though for bubble sort, it can be implemented directly in main for simplicity).

Use Cases or Case Studies

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

• Leaderboards and Rankings: Arranging scores in a game or competition from highest to lowest or lowest to highest.
• Price Listings: Organizing product lists on e-commerce websites by price, from lowest to highest or vice-versa.
• Alphabetical Ordering: Sorting names, file directories, or dictionary entries alphabetically for easy navigation.
• Data Preprocessing: Before applying more complex algorithms, data is often sorted to optimize search operations or identify patterns.
• Small Datasets: For very small arrays, where performance is not a critical concern, Bubble Sort can be a simple-to-implement solution.

Solution Approaches

The Bubble Sort algorithm is a straightforward method for sorting data.

Bubble Sort Algorithm

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until no swaps are needed, indicating that the list is sorted. Elements "bubble" up to their correct position with each pass.

// Bubble Sort using Array
#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j;
    // Outer loop for passes through the array
    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;
            }
        }
    }
}

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]);

    printf("Original array: ");
    printArray(arr, n);

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

    // Step 3: 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:

• Takes an integer array arr and its size n as input.
• The outer for loop (i) controls the number of passes. For an array of n elements, n-1 passes are sufficient. In each pass, the largest unsorted element "bubbles" to its correct position at the end of the unsorted portion.
• The inner for loop (j) iterates through the unsorted part of the array, comparing adjacent elements. n - i - 1 ensures that elements already placed at the end (due to previous passes) are not re-compared.
• Comparison and Swap: if (arr[j] > arr[j+1]) checks if the current element is greater than the next element. If true, they are in the wrong order for ascending sort, so they are swapped using a temporary variable temp.

1. printArray Function:

• A utility function to simply print the contents of an array.

1. main Function:

• Declares and initializes an integer array arr with unsorted values.
• Calculates the size n of the array using sizeof.
• Prints the Original array to show its initial state.
• Calls bubbleSort(arr, n) to perform the sorting operation.
• Prints the Sorted array to display the result after sorting.

Conclusion

Bubble Sort is a simple sorting algorithm to understand and implement, making it an excellent starting point for learning about sorting concepts. It repeatedly compares and swaps adjacent elements until the entire list is in order. While it is not efficient for large datasets due to its time complexity (O(n²)), its straightforward logic helps in grasping fundamental sorting principles.

Summary

• Bubble Sort sorts an array by repeatedly swapping adjacent elements that are in the wrong order.
• It performs n-1 passes, with each pass placing the largest unsorted element into its correct final position.
• The algorithm involves nested loops: an outer loop for passes and an inner loop for comparisons and swaps.
• Bubble Sort is easy to implement but inefficient for large arrays due to its quadratic time complexity.
• It serves as a valuable educational tool for understanding basic sorting mechanics.