Sorting Algorithms: Implementations and Analysis

A High-Level Glimpse

Before we dive into each one, let's look at a visual summary of their core strategies. Each algorithm approaches the problem of sorting differently.

We will now explore each of these in detail. For the core explanations, we'll rely on an excellent video that walks through the intuition, implementation logic, and complexity of all three.

1. Selection Sort: Select the Minimum

The core idea of Selection Sort is straightforward:

1. Find the smallest element in the entire unsorted array.
2. Swap it with the element at the first position.
3. Now, the first position is sorted. Move to the second position.
4. Find the smallest element in the rest of the unsorted array (from the second position onwards).
5. Swap it with the element at the second position.
6. Repeat this process until the entire array is sorted.

Essentially, in each pass i, you are "selecting" the correct element that should be at index i and putting it there.

Explanation and Dry Run

Java Implementation

Here is a clean Java implementation of Selection Sort. Notice how it directly maps to the logic described in the video.

public class Sorting {
    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;
        }
    }
}

Analysis

• Time Complexity: O(n²) for all cases (Best, Average, Worst).
  • The outer loop runs $n-1$ times.
  • The inner loop runs approximately $n$, then $n-1$, $n-2$, ..., 1 times. This series sums up to $n(n-1)/2$, which is O(n²).
  • Even if the array is already sorted (best case), the algorithm must still scan the entire unsorted portion to confirm that the current element is indeed the minimum. It has no way to exit early.
• Space Complexity: O(1). It's an in-place algorithm; we only need one temporary variable for the swap.
• Stability: Selection Sort is not stable. If you have two equal elements, their relative order might change. For example, in [5a, 5b, 2], the first pass will swap 2 with 5a, resulting in [2, 5b, 5a]. The original order of 5a and 5b has been reversed.
• Swaps: It performs at most $n-1$ swaps, which is the minimum among these three algorithms. This can be an advantage if write operations are significantly more expensive than read operations.

2. Bubble Sort: Swap Adjacent Elements

Bubble Sort works by repeatedly stepping through the list, comparing each pair of adjacent items, and swapping them if they are in the wrong order. After the first pass, the largest element will have "bubbled" up to its correct position at the end of the array.

Explanation and Dry Run

A crucial feature of Bubble Sort is the ability to optimize it. If we complete a full pass through the array without making a single swap, we know the array is already sorted and we can stop early.

Java Implementation

This implementation includes the "swapped" flag optimization.

public class Sorting {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            // The last i elements are already in place
            for (int j = 0; j < n - 1 - i; 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;
                    swapped = true;
                }
            }
            // If no two elements were swapped by inner loop, then break
            if (!swapped) {
                break;
            }
        }
    }
}

Analysis

• Time Complexity:
  • Worst and Average Case: O(n²). This occurs when the array is in reverse order, requiring the maximum number of passes and swaps.
  • Best Case: O(n). If the array is already sorted, the algorithm will make one pass, find that no swaps are needed, and exit.
• Space Complexity: O(1). It is also an in-place algorithm.
• Stability: Bubble Sort is stable. Since it only swaps adjacent elements if the first is strictly greater than the second, the relative order of equal elements is never changed.

3. Insertion Sort: Insert into Sorted Position

Insertion Sort builds the final sorted array one item at a time. It's conceptually similar to how many people sort a hand of playing cards.

1. Assume the first element is a sorted subarray of size 1.
2. Take the second element and insert it into the correct position within the sorted subarray (either before or after the first element).
3. Now you have a sorted subarray of size 2.
4. Take the third element and shift elements in the sorted subarray to the right until you find the correct position for it.
5. Repeat until all elements have been inserted.

Explanation and Dry Run

Insertion sort is particularly efficient for datasets that are already substantially sorted.

Java Implementation

The inner while loop is responsible for finding the correct insertion spot by shifting elements.

public class Sorting {
    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;
        }
    }
}

Analysis

• Time Complexity:
  • Worst and Average Case: O(n²). If the array is reverse-sorted, each element needs to be shifted all the way to the beginning of the sorted subarray.
  • Best Case: O(n). If the array is already sorted, the inner while loop condition arr[j] > key will be false immediately for every element. The algorithm just makes one pass to confirm this.
• Space Complexity: O(1). It is an in-place algorithm.
• Stability: Insertion Sort is stable.
• Adaptiveness: This is its key strength. It is an adaptive algorithm, meaning its performance improves when the input array is "partially sorted". Because of this, and its excellent performance on small n, it is often used as a component in more sophisticated hybrid sorting algorithms like Timsort (used in Python and Java) and Introsort.

4. Summary and Comparison

You've now seen the mechanics of all three basic sorting algorithms. While they all share a similar O(n²) average-case complexity, their characteristics make them suitable for different (mostly academic or niche) scenarios.

For a final consolidated view, I recommend reading this short article that compares them directly and summarizes their properties.

Here is a summary table based on what we've learned:

Conclusion

In this lesson, you implemented and analyzed three fundamental sorting algorithms. You are now equipped to discuss their mechanisms, performance trade-offs, and relative strengths and weaknesses—a common expectation in foundational DSA interviews.

Key Takeaways:

• Selection Sort minimizes swaps but has an O(n²) time complexity in all cases.
• Bubble Sort is simple but generally inefficient, though an optimized version can detect a sorted array in O(n) time.
• Insertion Sort is the most practical of the three, as it's adaptive and highly efficient for small or nearly sorted arrays.
• All three are in-place (O(1) space) but are too slow for general-purpose sorting on large datasets due to their O(n²) average-case complexity.

Preview of the next lesson:
The inefficiency of these O(n²) algorithms naturally leads to the question: "Can we do better?" The answer is a resounding yes! In our next lesson, we will begin exploring a new class of algorithms with O(n log n) time complexity. We will start with Merge Sort, a powerful and elegant algorithm based on the "divide and conquer" paradigm.