Selection Sort

Code

C language code:

#include <stdio.h>

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    selection_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Code Explanation

1. Initialization: The array arr is the array to be sorted, and n is the length of the array.
2. Main sorting loop:
   • The outer for loop controls the starting position of each pass, from element 0 to element n-2.
   • Initializes the minimum value index min_idx to the current starting position i.
   • The inner for loop traverses all elements after the starting position, finds the minimum value, and updates min_idx.
   • After finding the minimum value, swaps the element at the current starting position with the minimum value element.
3. Result output: After sorting is complete, the sorted array is printed.

Example Run

Assuming the input array is {64, 25, 12, 22, 11}:

1. Initial state: {64, 25, 12, 22, 11}
2. First outer loop (i=0):
   • Find minimum value 11 at index 4, swap 64 and 11: {11, 25, 12, 22, 64}
3. Second outer loop (i=1):
   • Find minimum value 12 at index 2, swap 25 and 12: {11, 12, 25, 22, 64}
4. Third outer loop (i=2):
   • Find minimum value 22 at index 3, swap 25 and 22: {11, 12, 22, 25, 64}
5. Fourth outer loop (i=3):
   • The remaining part is already sorted, no swap needed: {11, 12, 22, 25, 64}

Final result: {11, 12, 22, 25, 64}

Time Complexity Analysis

The time complexity of selection sort mainly depends on the number of executions of the two loops.

• Best-case time complexity: $O(n^2)$, even if the array is already sorted, $n(n-1)/2$ comparisons are still needed.
• Worst-case time complexity: $O(n^2)$, in the worst case, the same number of comparisons and swaps are performed.
• Average time complexity: $O(n^2)$, regardless of the initial order of the array, the number of executions is essentially the same.

Space Complexity Analysis

Selection sort is an in-place sorting algorithm that requires no additional auxiliary space, so the space complexity is $O(1)$. In this implementation, we only use a few extra variables (i, j, min_idx, temp), so the space complexity remains at a constant level.

Advantages and Disadvantages

Advantages:

• Simple and easy to implement.
• In-place sorting; low space complexity.
• Does not depend on initial data order; stable performance.

Disadvantages:

• High time complexity; especially inefficient for large-scale data.
• Unstable sorting algorithm; may change the relative order of equal elements.

Applicable Scenarios

Selection sort is suitable for the following scenarios:

• Sorting small datasets.
• When a simple and easy-to-understand sorting algorithm is needed.
• Learning and teaching purposes, to understand basic sorting principles.

Summary

Selection sort is a simple and intuitive sorting algorithm that works by repeatedly selecting the minimum value from the remaining elements and placing it at the end of the sorted portion. Although its time complexity is high, in specific scenarios, especially with small datasets, selection sort remains an effective choice.