Sorting Algorithms — Bubble Sort

Hi everyone! Welcome to my article on Sorting Algorithms part 2. In this blog, we’ll explore a most commonly used sorting algorithm; Bubble Sort. Let’s dive in!

If you want to know the basics of Sorting Algorithms, you can check out my article on Sorting Algorithms part 1 — Introduction to Sorting Algorithms.

Bubble Sort

Concept

Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order. The process is repeated until the list is sorted. The name “Bubble Sort” comes from the way smaller elements “bubble” to the top of the list.

Steps

1. Start at the beginning of the list.
2. Compare the first two elements.
3. If the first element is greater than the second, swap them.
4. Move to the next pair of elements and repeat the comparison and swapping process.
5. Continue until the end of the list. After the first pass, the largest element will be at the end.
6. Repeat the process for the remaining elements, excluding the last sorted elements.
7. Continue until no swaps are needed, indicating the list is sorted.

Implementation

Here’s a simple Java implementation of Bubble Sort:

public class BubbleSort {
    
    // Method to perform Bubble Sort
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped;
        
        // Loop through each element in the array
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            // Inner loop to compare and swap adjacent elements
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // Swap array[j] and array[j + 1]
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // If no elements were swapped in the inner loop, the array is sorted
            if (!swapped) break;
        }
    }
    
    // Main method to test the Bubble Sort
    public static void main(String[] args) {
        int[] array = {5, 1, 4, 2, 8};
        
        System.out.println("Unsorted array:");
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        // Sort the array using Bubble Sort
        bubbleSort(array);
        
        System.out.println("Sorted array:");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

Explanation

1. Initialization: The method bubbleSort takes an integer array as input.
2. Outer Loop: The outer loop iterates through the array. After each pass, the largest element in the unsorted portion moves to its correct position.
3. Inner Loop: The inner loop compares adjacent elements and swaps them if they are in the wrong order.
4. Swapping: If an element is greater than the next one, they are swapped.
5. Optimization: If no elements were swapped during a pass, the array is already sorted, and the algorithm breaks out of the loop early.
6. Main Method: The main method initializes an array, prints it, sorts it using Bubble Sort, and then prints the sorted array.

Complexity of Bubble Sort

Bubble Sort is not the most efficient sorting algorithm, especially for large datasets. Its performance is typically analyzed in terms of time complexity and space complexity.

Time Complexity

1. Best Case: O(n)

• The best case occurs when the array is already sorted. In this case, Bubble Sort can detect that no swaps are needed and break out of the loop early.
• This optimized behavior requires a flag to check if any swaps were made during a pass.

2. Average Case: O(n²)

• On average, Bubble Sort needs to perform n/2×nn/2 \times nn/2×n comparisons and swaps, where nnn is the number of elements in the array.
• This is because it goes through the entire array multiple times, performing a number of comparisons roughly proportional to the square of the array size.

3. Worst Case: O(n²)

• The worst case occurs when the array is sorted in reverse order. In this scenario, Bubble Sort has to perform the maximum number of comparisons and swaps.

Space Complexity: O(1)

• Bubble Sort is an in-place sorting algorithm, meaning it only requires a constant amount of additional memory space, regardless of the input size.
• It sorts the array by modifying the original array rather than using additional arrays or data structures.

Summary

Bubble Sort is a straightforward but inefficient sorting algorithm for large lists. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted. The Java implementation provided illustrates the basic steps and logic of Bubble Sort.

I hope this blog has helped you understand the Bubble Sort algorithm, its implementation and its complexity.

Thank you for reading! If you have any questions or feedback, feel free to leave a comment below. Happy coding!