Selection Sort Algorithm

What is Selection Sort?

Selection Sort is a simple comparison-based sorting algorithm. It divides the array into two parts:

• The sorted part at the beginning
• The unsorted part at the end

In each iteration, it selects the minimum element from the unsorted part and swaps it with the first unsorted element, growing the sorted section by one.

How Selection Sort Works

1. Start with the first element in the array.
2. Search for the smallest element in the rest of the array.
3. Swap the smallest element with the current position.
4. Move to the next position and repeat the process.
5. Continue until the entire array is sorted.

This method repeatedly selects the smallest remaining element — hence the name Selection Sort.

Time & Space Complexity

• Space Complexity: O(1) → In-place sorting
• Stable: ❌ No (can be made stable with extra steps)

When to Use Selection Sort

• When simplicity is more important than performance
• For small datasets or teaching purposes
• When data movement is costly, since it minimizes swaps (only one swap per pass)

Selection Sort – C++ Code Example

#include <iostream>
using namespace std;

// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Find the index of the minimum element
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the found minimum with the first element
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }

        // Print the array after each pass
        cout << "After pass " << i + 1 << ": ";
        for (int k = 0; k < n; k++) {
            cout << arr[k] << " ";
        }
        cout << endl;
    }
}

// Utility function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

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

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

    selectionSort(arr, n);

    cout << "Sorted array:\n";
    printArray(arr, n);

    return 0;
}

Output

Original array:
64 25 12 22 11 
After pass 1: 11 25 12 22 64 
After pass 2: 11 12 25 22 64 
After pass 3: 11 12 22 25 64 
After pass 4: 11 12 22 25 64 
Sorted array:
11 12 22 25 64 

Selection Sort – Visual Explanation (Step-by-Step)

We will sort:

[64, 25, 12, 22, 11]

Pass 1: i = 0

• Search for the smallest element → 11
• Swap 11 with 64
  → Result:

[11, 25, 12, 22, 64]

Pass 2: i = 1

• Search in [25, 12, 22, 64] → min = 12
• Swap 12 with 25
  → Result:

[11, 12, 25, 22, 64]

Pass 3: i = 2

• Search in [25, 22, 64] → min = 22
• Swap 22 with 25
  → Result:

[11, 12, 22, 25, 64]

Pass 4: i = 3

• Search in [25, 64] → min = 25 (already in place)
  → Result remains:

[11, 12, 22, 25, 64]

Final Sorted Array

[11, 12, 22, 25, 64]

Summary

• Selection Sort is simple and easy to implement.
• Always performs O(n²) comparisons, even when the array is nearly sorted.
• It’s in-place and performs minimal swaps.
• Best used for learning purposes or very small arrays.