Bubble sort program in c

Introduction of bubble sort program in c

Bubble sort program in c a process continues until no more swaps are needed, which means the list is sorted. This algorithm is simple to understand and implement but is not suitable for large datasets due to its time complexity. It is best used for small lists or as an educational tool to introduce bubble sorting concepts.

Characteristics of Bubble Sort program in c

• Comparison-based: Bubble Sort compares adjacent elements in the list.
• Stable: It maintains the relative order of elements with equal keys.
• In-Place: Bubble Sort requires only a small, constant amount of additional memory space.
• Time Complexity:
• Worst and Average Case: (O(n^2))

Basic Implementation of Bubble Sort program in C

Here’s the basic implementation of Bubble Sort in C:

#include <stdio.h>

// Function to perform Bubble Sort
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) { // Loop through all elements
        for (j = 0; j < n - i - 1; j++) { // Last i elements are already in place
            if (arr[j] > arr[j + 1]) { // Compare adjacent elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

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

int main() {
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the size of the array
    printf("Original array: \n");
    printArray(arr, n); // Print the original array

    bubbleSort(arr, n); // Call the bubbleSort function

    printf("Sorted array: \n");
    printArray(arr, n); // Print the sorted array
    return 0;
}

Explanation of the Functions

1. Function bubble Sort: This function takes an array arr[] and its size n as arguments. It uses two nested loops to compare and swap adjacent elements if they are in the wrong order.
2. main Function: Initializes an example array, calculates its size, and calls bubble Sort and printArray functions to demonstrate the sorting process.

Optimized Bubble Sort

The basic Bubble Sort algorithm can be optimized by observing that the algorithm doesn’t need to check all elements if no swaps were made in the inner loop, meaning the list is already sorted. Here is the optimized version:

#include <stdio.h>

// Optimized Bubble Sort function
void bubbleSortOptimized(int arr[], int n) {
    int i, j;
    int swapped;
    for (i = 0; i < n - 1; i++) {
        swapped = 0; // Reset swap flag at the start of each pass
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1; // Set swap flag to indicate a swap occurred
            }
        }
        // If no elements were swapped, the array is sorted
        if (swapped == 0) {
            break;
        }
    }
}

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);

    bubbleSortOptimized(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Key Modifications in the Optimized Code

• Swapped Flag: A boolean variable swapped is used to check whether any swaps were made during a pass. If no swaps occur, swapped remains 0, and the loop breaks early, reducing the number of passes.
• Early Termination: If swapped is 0 after any pass, the list is sorted, and we can terminate the algorithm early, improving performance for nearly sorted arrays.

Performance Analysis of Bubble Sort

Bubble Sort’s performance depends on the initial order of elements:

• Worst-Case Scenario: (O(n^2)) occurs when the array is in reverse order. Every element has to be compared with every other element, and a swap is made for each pair.
• Best-Case Scenario: (O(n)) occurs when the array is already sorted. The optimized version detects that no swaps were made and terminates after one pass.
• Average-Case Scenario: (O(n^2)) because, on average, elements are in random order.

Space Complexity

Bubble Sort is an in-place sorting algorithm, meaning it requires only a constant amount (O(1)) of additional memory space for variable storage.

Applications and Use Cases

• Educational Tool: Due to its simplicity, Bubble Sort is often used to introduce the concept of sorting algorithms.
• Small Datasets: Bubble Sort is efficient for sorting small datasets or lists that are already mostly sorted.
• Checking Sortedness: It can be used as a quick check to see if an array is sorted.