How Selection Sort Works

Selection Sort divides the array into a sorted sublist on the left and an unsorted sublist on the right. In each iteration, it finds the smallest (minimum) element in the unsorted sublist and swaps it with the first unsorted element.

---

C Implementation

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        /* Find minimum in remaining unsorted portion */
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        /* Swap with first element of unsorted sublist */
        if (minIndex != i) {
            swap(&arr[i], &arr[minIndex]);
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    selectionSort(arr, n);

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

    return 0;
}

Sample Output

text (ISO Standard)
Copy
Original Array:
29 10 14 37 13 
Sorted Array (Selection Sort):
10 13 14 29 37 

---

Complexity Analysis

• Time Complexity: O(n²) for best, average, and worst cases (always executes $(n(n-1) / 2)$ comparisons).
• Auxiliary Space: O(1) in-place algorithm.
• Swaps: Minimum swaps compared to Bubble Sort (O(n) swaps total).

---

Related Sorting Guides

• Compare with early exit optimization in Bubble Sort in C.
• Master pass-by-reference swapping in Swap Two Numbers in C.