Bubble Sort vs Selection Sort

In this post, we will learn the difference between Bubble Sort and Selection Sort in Java. This is a frequently asked question in Java interviews for beginners.

Sorting is a fundamental operation in computer science, and there are various algorithms available to accomplish this task efficiently. Two such algorithms are Bubble Sort and Selection Sort. In this blog post, we will explore the differences between Bubble Sort and Selection Sort, analyze their performance characteristics, and provide examples to demonstrate their implementations. 

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the entire list is sorted. 

Selection Sort is also a simple comparison-based sorting algorithm. It divides the input list into two parts: the sorted part and the unsorted part. The algorithm repeatedly finds the minimum (or maximum, depending on the sorting order) element from the unsorted part and moves it to the end of the sorted part.

Difference between  Bubble Sort and Selection Sort in Java

Feature	Bubble Sort	Selection Sort
Sorting Algorithm	Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly swaps adjacent elements if they are in the wrong order until the entire array is sorted.	Selection Sort is also a comparison-based sorting algorithm. It repeatedly selects the minimum element from the unsorted part of the array and places it at the beginning of the sorted part.
Time Complexity	The average and worst-case time complexity of Bubble Sort is O(n^2), where n is the number of elements in the array.	The average and worst-case time complexity of the Selection Sort is also O(n^2).
Best-Case Complexity	The best-case time complexity of Bubble Sort is O(n) when the array is already sorted. However, the algorithm still requires a pass through the entire array to detect if it is sorted, resulting in unnecessary iterations.	The best-case time complexity of the Selection Sort is also O(n^2) because it performs the same number of comparisons and swaps regardless of the initial order of the array.
Adaptive	Bubble Sort is an adaptive sorting algorithm. It can take advantage of already sorted portions of the array and terminate early if no swaps are performed during a pass.	Selection Sort is not adaptive. It performs the same number of comparisons and swaps regardless of the initial order of the array.
Stability	Bubble Sort is stable. It maintains the relative order of elements with equal keys as they appear in the original array.	Selection Sort is not stable. It may change the relative order of elements with equal keys during sorting.
Performance	Bubble Sort is less efficient compared to other sorting algorithms like Merge Sort or Quick Sort. It is not suitable for large arrays or performance-critical applications.	Selection Sort is also inefficient for large arrays due to its quadratic time complexity. It is generally used for small arrays or as an educational example of a sorting algorithm.
Space Complexity	Both Bubble Sort and Selection Sort have a space complexity of O(1) as they only require a constant amount of additional memory for temporary variables used in swapping elements.

Example

Example of Bubble Sort: Let's sort an array using Bubble Sort to illustrate how it works:

public class BubbleSort {
    public 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]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Example of Selection Sort: Let's sort an array using Selection Sort:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap arr[i] and arr[minIndex]
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Output:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Conclusion

In summary, Bubble Sort and Selection Sort are both simple comparison-based sorting algorithms with quadratic time complexity. Bubble Sort repeatedly swaps adjacent elements, while Selection Sort selects the minimum element and moves it to its correct position. Both algorithms have limitations in terms of efficiency and are generally not used for large datasets. For larger datasets, more efficient sorting algorithms like Merge Sort or Quick Sort are preferred.