Bubble Sort

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. Here’s how the Bubble Sort algorithm works:

Algorithm:

1. Start from the beginning of the array.
2. Compare each pair of adjacent elements.
3. If the elements are in the wrong order (e.g., the current element is greater than the next one), swap them.
4. Continue this process until the end of the array is reached.
5. Repeat the above steps for each element in the array until the entire array is sorted.

Here’s the Bubble Sort algorithm implemented 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++) {
        // Last i elements are already in place, so no need to check them
        for (j = 0; j < n - i - 1; j++) {
            // Traverse the array from 0 to n-i-1
            // Swap if the element found is greater than the next element
            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");
}

// Driver program to test above functions
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);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Output:

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

Time Complexity

The time complexity of the Bubble Sort algorithm is O(n^2) in the worst-case scenario, where n is the number of elements in the array.

Here’s why the time complexity is O(n^2):

• Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
• In the worst-case scenario, when the array is in reverse order, Bubble Sort will have to perform a maximum number of comparisons and swaps.
• For each element in the array, Bubble Sort compares it with every other element in the array, resulting in n * (n – 1) / 2 comparisons in total.
• Therefore, the number of comparisons and swaps required to sort the array is proportional to n^2.
• As a result, the time complexity of Bubble Sort is O(n^2).