Bubble Sort vs Selection Sort

These are “Simple Comparison Based Sorting Algorithms”.

Bubble Sort:

Bubble Sort is a straightforward sorting algorithm that compares adjacent elements in an array and swaps them if they are in the wrong order. This process is repeated until the entire array is sorted. Although not the most efficient sorting algorithm for large datasets, Bubble Sort is easy to understand and implement, making it a valuable introductory example in algorithmic studies.

Given below is the reference code for bubble sort in JAVA.

Code:

public class BubbleSort {

    // Performing Bubble Sort
    public static void bubbleSort(int[] arr) {
        int n = arr.length;

        // Traversing through the array
        for (int i = 0; i < n; i++) {
            // Last i elements are already sorted, so no need to check them
            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]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    // Method to swap two elements in an array
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] myArray = {64, 34, 25, 12, 22, 11, 90};

        // Performing Bubble Sort
        bubbleSort(myArray);

        // Displaying the sorted array
        System.out.print("Sorted array: ");
        for (int num : myArray) {
            System.out.print(num + " ");
        }
    }
}

Code Explanation:

• The outer loop runs through the entire list, and the inner loop compares adjacent elements and swaps them if they are in the wrong order.
• After each pass of the outer loop, the largest unsorted element settles at the end.
• The process repeats until the entire list is sorted.

Time Complexity: O(n²). [n is the number of elements in the array]

Selection Sort:

Selection Sort is an uncomplicated yet effective sorting algorithm. It operates by repeatedly identifying the minimum element from the unsorted portion of an array and relocating it to the beginning. Although not the most efficient algorithm for large datasets, Selection Sort is a valuable learning example due to its simplicity and intuitive operation.

Given below is the reference code for selection sort in JAVA.

Code:

public class SelectionSort {

    // Performing Selection Sort
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // Traverse through the array
        for (int i = 0; i < n; i++) {
            // Find the minimum element in the unsorted part of the array
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap the found minimum element with the first element
            swap(arr, i, minIndex);
        }
    }

    // Method to swap two elements in an array
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] myArray = {64, 25, 12, 22, 11};

        // Performing Selection Sort
        selectionSort(myArray);

        // Displaying the sorted array
        System.out.print("Sorted array: ");
        for (int num : myArray) {
            System.out.print(num + " ");
        }
    }
}

Code Explanation:

• The outer loop selects an element from the unsorted part of the array.
• The inner loop finds the minimum element in the remaining unsorted part.
• The minimum element is then swapped with the first element of the unsorted part.

Time Complexity: O(n²). [n is the number of elements in the array]

Which sorting algorithm should be used between “Bubble Sort and Selection Sort”?

Bubble Sort:

• Bubble Sort performs well when the input array is nearly sorted because it only swaps adjacent elements.
• It is straightforward to understand and implement, making it a good choice for educational purposes or small datasets.
• In terms of practical performance, Bubble Sort is generally less efficient than other sorting algorithms for large datasets.

Selection Sort:

• Selection Sort has a constant time complexity for selecting the minimum element in each pass, making it slightly more efficient than Bubble Sort in practice.
• It performs consistently across different scenarios, and its simplicity makes it a reasonable choice for small to moderately-sized datasets.

Conclusion:

Selection Sort may be preferred over Bubble Sort.

THANKS FOR READING ❤️