Selection Sort repeatedly selects the smallest element and places it in its correct position.

• Start from the first element of the array.
• Assume the current element is the smallest.
• Compare it with all the remaining elements in the unsorted part of the array.
• Find the smallest element.
• Swap the smallest element with the first unsorted element.
• Move to the next position and repeat the process until the array is sorted.

SelectionSort(arr, n)
 
for i = 0 to n - 2 do
    min = i
    for j = i + 1 to n - 1 do
        if arr[j] < arr[min] then
            min = j
    end for
 
    if min != i then
        swap arr[i] and arr[min]
    end if
end for

Selection Sort is a sorting algorithm that repeatedly:

• finds the minimum element from the unsorted part,
• places it at the beginning.

Input: 96 43 74 72 46
Output: 43 46 72 74 96

arr[0] = 96
arr[1] = 43
arr[2] = 74
arr[3] = 72
arr[4] = 46

Pass 1:

• Minimum = 43
• Swaps arr[1] = 43 and arr[0] = 96
• Result: 43 96 74 72 46

Pass 2:

• Minimum = 46
• Swaps arr[4] = 46 and arr[1] = 96
• Result: 43 46 74 72 96

Pass 3:

• Minimum = 72
• Swaps arr[3] = 72 and arr[2] = 74
• Result: 43 46 72 74 96

Pass 4:

• Minimum = 74
• Result: 43 46 72 74 96

#include <iostream>
 
using namespace std;
 
void selectionSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int idx = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[idx])
            {
                idx = j;
            }
        }
 
        swap(arr[i], arr[idx]);
    }
}
 
void printArray(int arr[], int n, string msg = "")
{
    cout << msg << endl;
 
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
int main()
{
 
    int arr[] = {5, 16, 4, 71, 2, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printArray(arr, n, "Original array:");
 
    selectionSort(arr, n);
    printArray(arr, n, "Sorted array(asc):");
 
    return 0;
}   

Original array:
5 16 4 71 2 11
Sorted array(asc):
2 4 5 11 16 71

Best, Average, Worst: O(n2) Because:

• Two nested loops are always used.
• Number of comparisons does not depend on input order.

No, Equal elements may change their relative order after swapping.

Example:

2a  2b  1
 
After sorting:
1  2b  2a

No, Even if array is already sorted, it still performs all comparisons.

Because in every pass:

• it selects the minimum element
• and places it in correct position.

Maximum: n - 1

Unlike Bubble Sort, Selection Sort performs fewer swaps.

Because:

• it minimizes swaps,
• useful when swapping cost is expensive.

Example:

• EEPROM memory
• Flash storage systems

Because:

• Time complexity is always quadratic. O(n2)
• Algorithms like Merge Sort and Quick Sort are much faster.

No, It always performs: n * (n - 1 ) / 2 comparisons.

Because:

• swaps are expensive,
• selection Sort minimizes writes/swaps.

• place minimum element first,
• recursively sort remaining array.