Sorting Algorithms

Selection Sort: Always Finding the Minimum

An efficient approach to minimizing swaps by repeatedly selecting the smallest element.

What is Selection Sort?

Selection Sort is an in-place comparison sorting algorithm that works by dividing the input list into two parts: a sorted sublist on the left, and an unsorted sublist on the right. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.

The algorithm proceeds by repeatedly finding the minimum element from the unsorted sublist and swapping it with the leftmost element of the unsorted sublist, thereby moving the boundary one element to the right. This methodical search and single swap per pass is the hallmark of Selection Sort.

Step-by-Step Visualization of All Passes

Let's trace the Selection Sort algorithm on the array $\text{arr}[] = \{64, 25, 12, 22, 11\}$. The sorted subarray grows from left to right as the minimum element is placed.

Pass 1 (i=0): Current Element is 64

We scan the entire array and find the minimum element, which is **11**. We swap $\mathbf{11}$ with the element at the current position, $\mathbf{64}$.

Array State: $\textbf{\{11\}}, 25, 12, 22, 64$

Pass 2 (i=1): Current Element is 25

The unsorted portion is $\{25, 12, 22, 64\}$. The minimum element found is **12**. We swap $\mathbf{12}$ with the current element $\mathbf{25}$.

Array State: $\textbf{\{11, 12\}}, 25, 22, 64$

Pass 3 (i=2): Current Element is 25

The unsorted portion is $\{25, 22, 64\}$. The minimum element found is **22**. We swap $\mathbf{22}$ with the current element $\mathbf{25}$.

Array State: $\textbf{\{11, 12, 22\}}, 25, 64$

Final Steps (Passes 4 and 5)

In the remaining passes, the minimum element of the unsorted subarray is already in the correct position (25 at $i=3$ and 64 at $i=4$), so no actual swaps are needed. The array is fully sorted.

Final Sorted Array: $\{11, 12, 22, 25, 64\}$

Selection Sort Algorithm (Pseudocode)

procedure selectionSort( A : list of sortable items )
    n = length(A)
    // Outer loop iterates through all elements to be placed
    for i from 0 to n-2 do
        minIndex = i
        // Inner loop finds the index of the minimum element in the remaining unsorted array
        for j from i+1 to n-1 do
            if A[j] < A[minIndex] then
                minIndex = j
            end if
        end for
        
        // Swap the found minimum element with the current element A[i]
        // This ensures A[i] is now in its correct sorted position
        swap( A[i], A[minIndex] )
        
    end for
end procedure

Complexity Analysis of Selection Sort

Like Bubble Sort, Selection Sort uses nested loops, which directly impacts its scalability, but it distinguishes itself by strictly limiting the number of write operations (swaps).

Time Complexity:

$O(n^2)$

Best, Worst, and Average Case. The algorithm always performs $O(n^2)$ comparisons because it must search the entire remaining unsorted list in every pass.

Auxiliary Space:

$O(1)$

It only requires a single temporary variable for swapping, making it an in-place sort.

Please refer Complexity Analysis of Selection Sort for detailed breakdowns.

Advantages

• It's easy to understand and implement, just like Bubble Sort.
• It is an In-place sorting algorithm with $O(1)$ auxiliary space.
• It performs the minimum number of swaps ($n-1$ at most), which is critical when writing data to memory (or disk) is a costly operation.

Disadvantages

• It has a time complexity of $O(n^2)$, making it very slow and inefficient for large data sets.
• It is an unstable sorting algorithm, meaning it doesn't guarantee the relative order of equal elements is preserved.
• Unlike Bubble Sort, its runtime is *not* sensitive to the initial order of the data; it always takes $O(n^2)$ time.

C Program Implementation

#include <stdio.h>

// Function to swap two elements
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Function to implement Selection Sort
void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++) {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }

        // Swap the found minimum element with the first element of the unsorted subarray
        if (min_idx != i) {
            swap(&arr[min_idx], &arr[i]);
        }
    }
}

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

// Driver code to test the function
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array (using Selection Sort): \n");
    printArray(arr, n);

    return 0;
}

The C implementation shows the nested loop structure clearly. The inner loop finds the index of the minimum element, and the swap is performed only once per pass of the outer loop, minimizing write operations.

Final Thoughts on Selection Sort

Selection Sort is often preferred over Bubble Sort in niche scenarios where minimizing memory writes (swaps) is more important than the overall execution time. It offers a clear, predictable approach to sorting that's invaluable for understanding the trade-offs in algorithm design.