Key differences between Bubble Sort and Selection Sort

Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name because smaller elements “bubble” to the top of the list (beginning) with each pass, while larger elements sink to the bottom (end). It is known for its simplicity but is not suitable for large data sets as its average and worst-case time complexity is O(^n2), where 𝑛n is the number of items being sorted. Despite its inefficiency, it’s a popular algorithm for teaching sorting mechanisms.

Functions of Bubble Sort:

• Simple to Understand and Implement:

Bubble Sort is one of the easiest sorting algorithms to understand and code, making it a frequent teaching tool in introductory computer science courses.

• Detects Sorted List Early:

With an optimized version that checks for swaps in each pass, Bubble Sort can detect if the list is already sorted and terminate early, potentially reducing its time complexity in best-case scenarios.

• Stable Sorting:

Bubble Sort is a stable sort; it maintains the relative order of records with equal keys (i.e., values).

• In-Place Sorting:

Requires no additional storage beyond the original array, as it only uses extra space for swapping elements.

• Comparative Algorithm:

Compares each pair of adjacent items and swaps them if they are in the wrong order, which is characteristic of comparative sorting algorithms.

• Fixed Space Requirement:

Only a small, constant amount of additional memory space is needed, specifically for the temporary variable used during the swapping of elements.

• Performance:

Despite having a poor average and worst-case performance of O(n^2), it is adequate for small datasets or nearly sorted arrays where fewer passes will be needed.

• Adaptable to Parallel Execution:

Algorithm can be adapted for parallel execution where each pair of adjacent elements can potentially be compared and swapped simultaneously, although this is less common in practical applications due to its inherent inefficiencies.

Example of Bubble Sort:

This example also includes an optimization to stop early if the array becomes sorted before making all the passes:

public class BubbleSortExample {

    public static void bubbleSort(int[] array) {

        int n = array.length;

        boolean swapped;

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

            swapped = false;

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

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

                    // swap temp and array[i]

                    int temp = array[j];

                    array[j] = array[j + 1];

                    array[j + 1] = temp;

                    swapped = true;

                }

            }

            // IF no two elements were swapped by inner loop, then break

            if (!swapped)

                break;

        }

    }

    public static void main(String[] args) {

        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        bubbleSort(arr);

        System.out.println(“Sorted array”);

        for (int i : arr) {

            System.out.print(i + ” “);

        }

    }

}

Explanation:

• Outer Loop:

Runs n−1 times, where 𝑛n is the number of elements in the array.

• Inner Loop:

Goes through the array from the start to n−i−1. It compares each pair of adjacent items and swaps them if they are in the wrong order.

• Swapped Flag:

A boolean flag checks if any elements were swapped during the inner loop’s execution. If no elements were swapped, the array is already sorted, and the algorithm can terminate early to save computation time.

Selection Sort

Selection Sort is a straightforward comparison-based sorting algorithm that works by repeatedly finding the minimum element (considering ascending order) from the unsorted portion of the list and moving it to the beginning. The process starts by selecting the first element as the minimum, scanning through the list to find a true minimum, then swapping it with the first position. This procedure is repeated for each position in the array, moving the boundary of the unsorted array one element forward each time. While simple and easy to understand, Selection Sort has a time complexity of (𝑛^2), making it inefficient for large datasets. It performs well on small lists and provides a clear demonstration of sorting techniques in computer science education.

Functions of Selection Sort:

• In-Place Sorting:

Selection sort performs the sorting within the given array without requiring additional memory or space, making it a space-efficient algorithm.

• Unstable Sorting:

It may change the relative order of elements with equal keys. Thus, it is not stable by default, but can be modified to be stable.

• Minimum Selection:

In each iteration, it selects the smallest element from the unsorted part of the array and places it at the beginning of the unsorted segment.

• Iterative Comparisons:

It iterates through the array, comparing elements to find the minimum element in each pass through the remaining unsorted section.

• Fixed Number of Passes:

The number of passes in a selection sort is always fixed at 𝑛−1n−1 for an array of 𝑛n elements, regardless of the order of the input data.

• Low Performance in Large Lists:

Due to its quadratic time complexity, typically (𝑛2)O(n2), selection sort is inefficient on large lists compared to more advanced sorting algorithms like quicksort or mergesort.

• Simplicity:

One of the simplest sorting algorithms to understand and implement, making it suitable for educational purposes or small datasets.

• Minimal Writes:

This algorithm performs the minimum possible number of writes (swap operations) since it makes only one swap for each pass through the array. This can be particularly useful where write operation is a costly affair.

Example of Selection Sort:

This example demonstrates sorting an array of integers in ascending order using the Selection Sort technique.

public class SelectionSortExample {

    public static void selectionSort(int[] arr) {

        int n = arr.length;

        // One by one move boundary of unsorted subarray

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

            // Find the minimum element in unsorted 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

            int temp = arr[minIndex];

            arr[minIndex] = arr[i];

            arr[i] = temp;

        }

    }

    public static void main(String[] args) {

        int[] arr = {64, 25, 12, 22, 11};

        selectionSort(arr);

        System.out.println(“Sorted array”);

        for (int i : arr) {

            System.out.print(i + ” “);

        }

    }

}

How it works:

• The selectionSort function loops through each index of the array.
• For each index i, it finds the smallest number from the index i to the end of the array.
• It then swaps this smallest number found with the number at the current index i.
• This process is repeated until the entire array is sorted in ascending order.

In this example, when the main method runs, it initializes an array of integers, sorts them using the selectionSort method, and finally prints the sorted array. The output for the provided array will be:

Sorted array

11 12 22 25 64

Key differences between Bubble Sort and Selection Sort

Key Similarities between Bubble Sort and Selection Sort

• In-Place Sorting:

Both sorting algorithms operate in-place, meaning they do not require additional memory proportional to the input size, aside from a small constant amount of additional memory space.

• Time Complexity:

Both have quadratic average and worst-case time complexities of O(n^2), making them less efficient for large datasets compared to more advanced sorting algorithms like quicksort or mergesort.

• Simplicity:

Both algorithms are conceptually simple and easy to understand, which makes them popular choices for introductory computer science courses to teach the fundamentals of sorting.

• Non-Recursive:

They are iterative in nature and do not use recursive calls, which simplifies their implementation and understanding.

• Space Complexity:

Each has a constant space complexity of O(1), due to their in-place sorting mechanism.

• Algorithm Type:

Both are comparison-based sorting algorithms, meaning they sort data by comparing elements.