Sorting Algorithms: Selection, Bubble, and Insertion

1. Selection Sort

The core idea of Selection Sort is straightforward and intuitive. For an array of n elements, you make n-1 passes. In each pass, you select the smallest remaining element from the unsorted part of the array and swap it with the element at the beginning of the unsorted part.

The process is as follows:

1. Pass 1: Find the minimum element in the entire array (arr[0] to arr[n-1]) and swap it with the element at index 0. After this pass, the first element is sorted.
2. Pass 2: Find the minimum element in the rest of the array (arr[1] to arr[n-1]) and swap it with the element at index 1. Now the first two elements are sorted.
3. Continue: Repeat this process for n-1 passes. After the i-th pass, the first i elements of the array will be sorted.

Let's start by watching a detailed explanation and walkthrough of the algorithm.

The takeUforward article below provides a written version of this logic, including a clear dry run with diagrams that you can refer to.

Implementation in Java

Here is the Java implementation of Selection Sort. Notice the two nested loops. The outer loop (i) iterates through the passes, marking the boundary between the sorted and unsorted parts. The inner loop (j) iterates through the unsorted part to find the index of the minimum element.

public class SortingAlgorithms {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // One by one, move the boundary of the unsorted subarray
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the 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
            // of the unsorted part.
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

Complexity Analysis

• Time Complexity: $O(n^2)$
  The algorithm consists of two nested loops. The outer loop runs n-1 times. The inner loop runs n-1 times in the first pass, n-2 in the second, and so on. The total number of comparisons is approximately $(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}$, which is $O(n^2)$. This is true for the best, average, and worst cases because the algorithm always makes the same number of comparisons, regardless of the initial order of the elements.
• Space Complexity: $O(1)$
  The sorting is done "in-place," meaning it does not require any significant extra memory besides a temporary variable for swapping.

2. Bubble Sort

Bubble Sort is another simple sorting algorithm, famous for its name. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. With each pass, the largest unsorted element "bubbles" up to its correct position at the end of the unsorted section.

The process is:

1. Pass 1: Iterate from the first element to the second-to-last. Compare arr[j] with arr[j+1] and swap if arr[j] > arr[j+1]. After this pass, the largest element will be at the last position.
2. Pass 2: Repeat the process, but this time, you only need to iterate up to the third-to-last element, as the last one is already in place. After this pass, the second-largest element is in its correct position.
3. Continue: Repeat for n-1 passes.

The following image illustrates one pass of Bubble Sort.

The take U forward video provides a great walkthrough of this process.

Implementation and Optimization

A key optimization for Bubble Sort is to recognize that if a full pass is completed with no swaps, the array must be sorted, and the algorithm can terminate early. This makes Bubble Sort efficient for arrays that are already nearly sorted.

The workat.tech article provides a good summary and code.

For a Java-specific coding demonstration, the following video is very helpful. It walks through building the code from scratch and addresses a common off-by-one error.

Complexity Analysis

• Time Complexity:
  • Worst and Average Case: $O(n^2)$. This occurs when the array is in reverse order.
  • Best Case: $O(n)$. This occurs when the array is already sorted. The optimized version will make a single pass, find that no swaps are needed, and terminate.
• Space Complexity: $O(1)$. It is an in-place sorting algorithm.

3. Insertion Sort

Insertion Sort builds the final sorted array one item at a time. It's much like how many people sort a hand of playing cards. You maintain a sorted sub-array at the beginning of the list. You then take the first element from the unsorted part and insert it into its correct position within the sorted part by shifting other elements to the right.

The process is:

1. Start with the second element (i=1). Consider the first element (arr[0]) to be a sorted sub-array of size 1.
2. Take the current element arr[i] (the "key") and compare it with elements in the sorted sub-array to its left (arr[j] where j < i).
3. Shift all elements in the sorted sub-array that are greater than the key one position to the right.
4. Insert the key into the newly created space.
5. Repeat for all elements up to n-1.

This image provides a great visual for the step-by-step execution.

Let's watch the video explanation to see it in action.

Implementation in Java

Here is a typical Java implementation. The outer loop picks the element to be inserted, and the inner while loop finds the correct position by shifting elements.

public static void insertionSort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        /* Move elements of arr[0..i-1], that are
           greater than key, to one position ahead
           of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Complexity Analysis

• Time Complexity:
  • Worst and Average Case: $O(n^2)$. The worst case occurs when the array is sorted in reverse order.
  • Best Case: $O(n)$. The best case occurs when the array is already sorted. The inner while loop's condition will always be false, so it only performs n-1 comparisons.
• Space Complexity: $O(1)$. It is an in-place sorting algorithm.

Insertion sort is particularly efficient for small datasets and for datasets that are already substantially sorted. For this reason, it's often used as a component in more sophisticated hybrid algorithms like Timsort (used in Java's Arrays.sort() for objects) and Introsort.

Summary of Simple Sorts

Here is a quick summary of the three algorithms we've covered today. While all have an average time complexity of $O(n^2)$, their best-case performance and behavior differ.

(We will cover the concept of "stability" in a future lesson, but it relates to how algorithms handle equal elements.)

Conclusion

In this lesson, you've learned to implement three fundamental sorting algorithms: Selection Sort, Bubble Sort, and Insertion Sort. You've seen how they work, analyzed their performance, and written their Java code.

Key Takeaways:

• Selection Sort: Works by repeatedly selecting the minimum element. Its performance is consistent across all cases at $O(n^2)$.
• Bubble Sort: Works by repeatedly swapping adjacent elements. It's notable for its ability to terminate early, giving it a best-case performance of $O(n)$.
• Insertion Sort: Works by building a sorted sub-array. Like Bubble Sort, it has a best-case time of $O(n)$ and is very effective on data that is already mostly sorted.

These $O(n^2)$ algorithms provide a crucial foundation. However, for the large datasets you'd encounter in real-world applications or competitive programming, they are too slow.

In our next lesson, we will make a significant leap in efficiency by studying Merge Sort. It is a powerful algorithm that uses a "divide and conquer" strategy to achieve a much better time complexity of $O(n\log n)$.