Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is called "bubble sort" because the smaller elements "bubble" to the top (or beginning) of the list during each iteration. It is a straightforward and intuitive algorithm, but it is not efficient for large data sets.

Here's an explanation of the bubble sort algorithm:

2. Compare the first element with the second element. If they are in the wrong order (e.g., the first element is greater than the second), swap them.

3. Move to the next pair of elements (the second and the third), and compare them. Again, swap them if they are in the wrong order.

4. Repeat this process for every pair of adjacent elements in the list until you reach the end.

5. After the first iteration, the largest element will have moved to the last position.

6. Repeat steps 2-5 for the remaining unsorted portion of the list (excluding the last element, which is already sorted).

7. Continue this process until the entire list is sorted.

Here's an example implementation of the bubble sort algorithm 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++) {
        for (j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements and swap if necessary
            if (arr[j] > 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 n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Test the algorithm
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    bubbleSort(arr, n);

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

    return 0;
}

In this example, the `bubbleSort` function performs the bubble sort algorithm on the given array. The `printArray` function is used to display the array before and after sorting. In the `main` function, we create an array, print it, call `bubbleSort` to sort the array, and then print the sorted array.

The output will be:

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

As you can see, the bubble sort algorithm gradually moves the larger elements to the end of the array, resulting in a sorted array.

Time Complexity

The time complexity of the Bubble Sort algorithm is O(n^2) in the worst and average cases, and O(n) in the best case.

In the worst case, when the input array is in reverse order, Bubble Sort needs to make n passes through the array, and for each pass, it compares and swaps adjacent elements. This results in a total of (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2) comparisons and swaps.

In the best case, when the input array is already sorted, Bubble Sort still needs to make one pass through the array to confirm that it is sorted, but it doesn't need to perform any swaps. In this case, the algorithm terminates early. Hence, the time complexity reduces to O(n).

The average case time complexity of Bubble Sort is also O(n^2), as it involves multiple passes through the array, performing comparisons and swaps.

It's worth noting that Bubble Sort is not considered efficient for large datasets, as other sorting algorithms like Quicksort or Mergesort have better average and worst-case time complexities. Bubble Sort is mainly used for educational purposes or when sorting small datasets where simplicity and code clarity are more important than efficiency.

Space Complexity

The space complexity of the Bubble Sort algorithm is O(1) because it uses a constant amount of extra space.

Bubble Sort operates directly on the input array without requiring additional data structures or dynamic memory allocation. It only needs a few variables to keep track of the indices and temporary values during the swapping process. Therefore, the space required by Bubble Sort remains constant, regardless of the size of the input array.

This makes Bubble Sort advantageous in terms of space complexity when compared to other sorting algorithms that may require additional arrays or data structures for auxiliary operations.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc