Selection Sort: Implementation & Complexity Analysis

Welcome to the next lesson on fundamental sorting algorithms. In our previous session, we implemented Bubble Sort, an algorithm that sorts an array by repeatedly swapping adjacent elements. We learned that while intuitive, its O(n²) time complexity makes it inefficient for large datasets.

Today, we'll explore Selection Sort, another algorithm in the O(n²) family. It uses a different strategy to achieve the same goal of sorting an array. This lesson will help you understand that different algorithmic approaches can exist for the same problem, each with its own nuances. You will learn to implement Selection Sort in C and analyze its time complexity.

1. The Selection Sort Strategy

The core idea of Selection Sort is to divide the array into two conceptual parts: a sorted part at the beginning and an unsorted part at the end. Initially, the sorted part is empty, and the unsorted part is the entire array.

The algorithm then iterates through the following steps:

1. Find the smallest element in the unsorted part of the array.
2. Swap it with the element at the beginning of the unsorted part.
3. Move the boundary between the sorted and unsorted parts one element to the right.

This process is repeated until the entire array is sorted. Let's start with a video that provides a great visual walkthrough of this process.

The image below provides another step-by-step visualization of the process. In each pass, the algorithm identifies the minimum element in the remaining unsorted portion (highlighted in blue) and swaps it with the first element of that portion (highlighted in orange).

2. Implementing Selection Sort in C

Now, let's translate this logic into C code. Similar to Bubble Sort, Selection Sort is naturally implemented with nested loops, but their roles are different:

• The outer loop iterates from the start of the array to the second-to-last element. Its counter (i) marks the boundary between the sorted and unsorted parts.
• The inner loop's job is to scan through the unsorted part of the array (from i+1 to the end) to find the index of the minimum element.
• After the inner loop completes, a single swap is performed to place the found minimum element at the correct position (i).

The same video we just watched provides a clear walkthrough of the C implementation.

Notice the key difference from Bubble Sort: Bubble Sort performs many swaps within its inner loop, whereas Selection Sort performs only one swap per pass of its outer loop.

3. Analyzing Time and Space Complexity

Time Complexity: O(n²)

To determine the time complexity, we count the number of comparisons. The nested loop structure is our main focus.

• In the first pass (when i = 0), the inner loop runs from j = 1 to n-1, making n-1 comparisons.
• In the second pass (when i = 1), the inner loop runs from j = 2 to n-1, making n-2 comparisons.
• ...
• In the final pass, it makes just 1 comparison.

The total number of comparisons is the sum of this series:

$$(n-1)+(n-2)+(n-3)+\cdots +1$$

This is the sum of the first $n-1$ integers, which has a well-known formula:

$$\frac{(n-1)\times n}{2}=\frac{n^2-n}{2}$$

In Big-O notation, we drop constants and lower-order terms, which leaves us with a time complexity of O(n²). The following video provides a detailed analysis.

A crucial point made in the video is that Selection Sort's performance is not affected by the initial order of the data. The loops must always run their full course to guarantee that the minimum element has been found. Therefore:

• Best-Case Complexity: O(n²) (e.g., an already sorted array)
• Worst-Case Complexity: O(n²) (e.g., a reverse-sorted array)
• Average-Case Complexity: O(n²) (e.g., a random array)

This is a key difference from the optimized Bubble Sort, which could exit early and achieve O(n) in the best case.

Space Complexity: O(1)

Selection Sort is an in-place algorithm. It sorts the array without needing to create a significant amount of auxiliary storage. It only requires a few extra variables for loop counters and the swap operation (min_idx, temp). Because this memory usage does not grow with the input size n, the space complexity is constant, or O(1).

4. Practice: Implementation and Modification

Now it's your turn to work with the code. Below is a clean implementation of Selection Sort in C.

Here is the complete code from the resource for you to experiment with:

#include <stdio.h>

// Function to swap the position of two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int array[], int size) {
    for (int step = 0; step < size - 1; step++) {
        int min_idx = step;
        for (int i = step + 1; i < size; i++) {
            // To sort in descending order, change > to < in this line.
            // Select the minimum element in each loop.
            if (array[i] < array[min_idx])
                min_idx = i;
        }
        // Put min at the correct position
        swap(&array[min_idx], &array[step]);
    }
}

// Function to print an array
void printArray(int array[], int size) {
    for (int i = 0; i < size; ++i) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

// Driver code to test the algorithm
int main() {
    int data[] = {20, 12, 10, 15, 2};
    int size = sizeof(data) / sizeof(data[0]);
    
    printf("Unsorted array:\n");
    printArray(data, size);

    selectionSort(data, size);

    printf("Sorted array in Ascending Order:\n");
    printArray(data, size);
}

Your Task:

1. Compile and run the code to confirm it sorts the array correctly.
2. Modify the selectionSort function to sort the array in descending (largest to smallest) order. As the comment in the code suggests, this only requires changing one character. This simple exercise will confirm your understanding of the core comparison logic.

Conclusion

You have now implemented and analyzed your second sorting algorithm, Selection Sort. By comparing it to Bubble Sort, you can see how different strategies can lead to algorithms within the same complexity class but with different performance characteristics (e.g., number of swaps).

Key Takeaways:

• Selection Sort works by repeatedly finding the minimum element in the unsorted portion and placing it at the end of the sorted portion.
• It uses nested loops, resulting in a time complexity of O(n²) for all cases (best, worst, and average).
• It performs significantly fewer swaps than Bubble Sort (at most n-1), which can be an advantage if swap operations are computationally expensive.
• Its space complexity is O(1) as it is an in-place sorting algorithm.

Preview of the Next Lesson:
We will continue our exploration of O(n²) sorting algorithms with Insertion Sort. You will discover that while it is also quadratic in the worst case, its structure makes it extremely efficient for lists that are already "mostly sorted," giving it a best-case complexity of O(n). This makes it a practical choice in certain real-world scenarios.