Bubble Sort Algorithm

This tutorial explains Bubble Sort, a fundamental sorting algorithm in computer science. It demonstrates the process of swapping adjacent elements to create a sorted list, making it an ideal starting point for beginners.

Understanding the Bubble Sort Algorithm

The Bubble Sort algorithm in computer science is a basic sorting technique for sorting lists or arrays in a specific order, typically ascending or descending. It works by repeatedly swapping adjacent elements if they are in the incorrect order. This process repeats until the entire list is sorted. Despite its simplicity, Bubble Sort is not the most efficient for large datasets but provides a foundational understanding of sorting algorithms.

Why It's Named Bubble Sort

Bubble Sort is named after the way elements move to their correct position in the list. In each iteration, the largest (or smallest, depending on the sorting order) unsorted element rises to its correct position in the array. This process is similar to bubbles rising to the surface of water.

How Bubble Sort Works

Let's assume you have an unsorted array - [5, 3, 8, 2, 1], and want to sort it in ascending order. Bubble sort works by repeatedly iterating through the array, comparing adjacent elements, and swapping them if they are in the incorrect order. This process is repeated until the array is fully sorted. For our example, the sorting process would involve several passes through the array, each time moving unsorted elements closer to their final position until achieving the sorted array - [1, 2, 3, 5, 8].

Implementation Examples

C++ Example

Implementing Bubble Sort in C++ is straightforward. The following code snippet demonstrates this process:

Example:

#include <iostream>
using namespace std;

// Function to perform bubble sort on the array
void bubbleSort(int arr[], int n) {
    // Loop for each element of the array except the last one
    for(int i = 0; i < n-1; i++) {
        // Inner loop for comparison and swapping
        // Goes up to the part of the array that hasn't been sorted yet
        for(int j = 0; j < n-i-1; j++) {
            // If the current element is greater than the next one, swap them
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

int main() {
    int arr[] = {5, 3, 8, 2, 1}; // Initial array
    int n = sizeof(arr)/sizeof(arr[0]); // Calculate the number of elements in the array
    bubbleSort(arr, n); // Call the bubbleSort function
    cout << "Sorted array: "; // Display the sorted array
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " "; // Print each element of the sorted array
    }
    return 0;
}

Output:

Sorted array: 1 2 3 5 8

Python Example

In Python, the Bubble Sort algorithm can be implemented as follows:

Example:

# Function to perform bubble sort on the array
def bubbleSort(arr):
    n = len(arr) # Get the number of elements in the array
    # Outer loop for traversing through each element of the array
    for i in range(n):
        # Inner loop for comparing adjacent elements
        # Goes up to the part of the array that hasn't been sorted yet
        for j in range(0, n-i-1):
            # If the current element is greater than the next one, swap them
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j] # Perform the swap

# Sample array of characters
arr = ['z', 'e', 'b', 'r', 'a']
bubbleSort(arr) # Call the bubbleSort function to sort the array
print("Sorted array is:", arr) # Print the sorted array

Output:

Sorted array is: ['a', 'b', 'e', 'r', 'z']

Java Example

Here's the Java code for implementing the Bubble Sort algorithm:

Example:

public class BubbleSort {
    
    // Method to perform bubble sort
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                // Swap if the element found is greater than the next element
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // IF no two elements were swapped by inner loop, then break
            if (!swapped)
                break;
        }
    }

    // Main method to test the bubbleSort method
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.print("Sorted array is: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output:

Sorted array is: 11 12 22 25 34 64 90

Time Complexity

The time complexity of Bubble Sort is O(n^2) in both average and worst-case scenarios, which means the time taken to sort the elements increases quadratically as the number of elements (n) grows. This complexity makes Bubble Sort inefficient for sorting large datasets compared to more advanced algorithms.

Conclusion

Bubble Sort is a simple yet effective sorting algorithm that is an excellent starting point for understanding how sorting works. Although it may not be the most efficient for practical applications, learning Bubble Sort is fundamental to grasping more complex sorting techniques. It emphasizes essential concepts like iteration and swapping, critical to many computer science algorithms.