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

1. What is Selection Sort?

Selection Sort is a sorting algorithm that repeatedly:

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

2. Dry Run Selection Sort.

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

3. Code Implementation

Example:

#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;
}   

Output:

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

4. What is the time complexity of Selection Sort?

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

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

5. What is the space complexity?

6. Is Selection Sort stable?

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

Example:

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

7. Is Selection Sort adaptive?

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

8. Why is Selection Sort called “Selection” Sort?

Because in every pass:

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

9. How many swaps occur in Selection Sort?

Maximum: n - 1

Unlike Bubble Sort, Selection Sort performs fewer swaps.

10. Why can Selection Sort be useful despite being slow?

Because:

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

Example:

• EEPROM memory
• Flash storage systems

11. Why is Selection Sort not preferred for large datasets?

Because:

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

12. Does Selection Sort reduce comparisons if array is already sorted?

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

13. Why is Selection Sort better than Bubble Sort in some cases?

Because:

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

14. Can Selection Sort be implemented recursively?

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