Sorting Algorithms in Java: Bubble, Selection, Insertion, Merge, and Quick Sort

Chapter 1: Bubble Sort in Java

1. Description of Bubble Sort (No Coding)

Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly swapping adjacent elements if they are in the wrong order. This process continues until the entire array is sorted. The algorithm gets its name because smaller elements gradually "bubble" to the top (beginning of the array), while larger elements sink to the bottom (end of the array).

Bubble Sort consists of multiple passes (iterations) through the array. Each pass ensures that the largest unsorted element moves to its correct position at the end of the array.

Working Principle of Bubble Sort

1. Start at the first element and compare it with the next element.
2. If the first element is greater than the second, swap them.
3. Move to the next adjacent pair and repeat step 2.
4. Continue this process until the last element is reached.
5. Repeat the process for the remaining unsorted part of the array.

Visualization Example:

Unsorted Array:

[5, 3, 8, 4, 2]

Pass 1:

• Compare 5 and 3, swap → [3, 5, 8, 4, 2]
• Compare 5 and 8, no swap → [3, 5, 8, 4, 2]
• Compare 8 and 4, swap → [3, 5, 4, 8, 2]
• Compare 8 and 2, swap → [3, 5, 4, 2, 8]

Pass 2:

• Compare 3 and 5, no swap → [3, 5, 4, 2, 8]
• Compare 5 and 4, swap → [3, 4, 5, 2, 8]
• Compare 5 and 2, swap → [3, 4, 2, 5, 8]

Pass 3:

• Compare 3 and 4, no swap → [3, 4, 2, 5, 8]
• Compare 4 and 2, swap → [3, 2, 4, 5, 8]

Pass 4:

• Compare 3 and 2, swap → [2, 3, 4, 5, 8]

Now, the array is sorted.

2. Bubble Sort Coding Examples

(a) Syllabus-Based Example (Sorting an array of numbers)

public class BubbleSortExample {

    static void bubbleSort(int arr[]) {

        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {

            for (int j = 0; j < n - i - 1; j++) {

                if (arr[j] > arr[j + 1]) {

                    int temp = arr[j];

                    arr[j] = arr[j + 1];

                    arr[j + 1] = temp;

                }

            }

        }

    }

    public static void main(String args[]) {

        int arr[] = {5, 3, 8, 4, 2};

        bubbleSort(arr);

        System.out.println(java.util.Arrays.toString(arr)); 

    }

}

Output:
[2, 3, 4, 5, 8]

(b) Real-World Example (Sorting student names alphabetically)

public class BubbleSortNames {

    static void bubbleSort(String arr[]) {

        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {

            for (int j = 0; j < n - i - 1; j++) {

                if (arr[j].compareTo(arr[j + 1]) > 0) {

                    String temp = arr[j];

                    arr[j] = arr[j + 1];

                    arr[j + 1] = temp;

                }

            }

        }

    }

    public static void main(String args[]) {

        String names[] = {"John", "Alice", "Bob", "Eve"};

        bubbleSort(names);

        System.out.println(java.util.Arrays.toString(names));

    }

}

Output:
[Alice, Bob, Eve, John]

3. Advantages of Bubble Sort (Pros)

✔ Simple and easy to implement – Best for beginners.
✔ Requires no extra space – It sorts the array in-place (O(1) space complexity).
✔ Can be optimized – Using a flag to stop early if no swaps occur in a pass.
✔ Stable sorting algorithm – Maintains the relative order of duplicate elements.
✔ Works well for nearly sorted data – Runs in O(n) time for nearly sorted arrays.

4. Disadvantages of Bubble Sort (Cons)

❌ Inefficient for large datasets – O(n²) time complexity makes it slow.
❌ Unnecessary comparisons and swaps – Even if the array is nearly sorted, it still does comparisons.
❌ Not suitable for real-world applications – Other sorting techniques like Quick Sort and Merge Sort are faster.
❌ Recursive approach is inefficient – Uses unnecessary function calls.
❌ Performance degrades with input size – Becomes impractical for large inputs.

5. How is Bubble Sort Better Than Other Sorting Techniques?

• Easier to understand and implement compared to Merge Sort or Quick Sort.
• Requires less memory (O(1) space) compared to Merge Sort (O(n) space complexity).
• Stable sorting – Maintains order of equal elements, unlike Quick Sort.
• Performs well on small or nearly sorted datasets, where Quick Sort’s O(n log n) overhead is unnecessary.
• Can be optimized to stop early if no swaps occur, reducing unnecessary iterations.

6. Best Cases to Use Bubble Sort

✔ When the dataset is already sorted or nearly sorted – Runs in O(n) time.
✔ When memory is limited – Requires no extra space, unlike Merge Sort.
✔ When stability is required – Maintains the order of duplicate elements.
✔ For educational purposes – Helps beginners understand sorting concepts.
✔ For small datasets – Works fine when n < 10.

7. Worst Cases to Use Bubble Sort

❌ When dealing with large datasets – Performance is O(n²), making it slow.
❌ When efficiency is required – Quick Sort and Merge Sort are faster.
❌ When dealing with real-world applications – Other sorting algorithms are preferred.
❌ When the dataset is completely reversed – This results in maximum swaps.
❌ When a high number of comparisons affects performance – Unnecessary comparisons slow it down.

Final Thoughts

Bubble Sort is one of the easiest sorting techniques but is highly inefficient for large datasets. While it can be optimized for small or nearly sorted arrays, it is not suitable for complex applications. In competitive programming and industry use cases, Quick Sort, Merge Sort, or Heap Sort are better alternatives. 🚀