DSA Selection Sort

DSA Selection Sort – Complete Beginner Guide

(Manual Run Through + Algorithm + Code + Time Complexity)

Selection Sort is a simple comparison-based sorting algorithm in DSA.
It repeatedly selects the smallest element from the unsorted part and places it at the correct position.

https://he-s3.s3.amazonaws.com/media/uploads/2888f5b.png

1️⃣ What is Selection Sort?

Selection Sort works by:

Dividing the array into sorted and unsorted parts
Finding the minimum element from the unsorted part
Swapping it with the first unsorted position

📌 After each pass, one element is placed correctly.

2️⃣ Simple Idea (One Line)

Select the smallest → place it at correct position → repeat

3️⃣ Selection Sort – Manual Run Through

🔹 Given Array

🔸 Pass 1

Minimum in entire array = 11
Swap with first element (64)

✅ 11 is now in correct position

🔸 Pass 2

Unsorted part: [25, 12, 22, 64]
Minimum = 12
Swap with 25

🔸 Pass 3

Unsorted part: [25, 22, 64]
Minimum = 22
Swap with 25

🔸 Pass 4

Unsorted part: [25, 64]
Minimum = 25
Already in place → no swap

✅ Final Sorted Array

4️⃣ Selection Sort Algorithm (Steps) ⭐⭐

Start
For i = 0 to n-2
Assume i is the index of minimum
For j = i+1 to n-1
- If arr[j] < arr[minIndex], update minIndex
Swap arr[i] and arr[minIndex]
Repeat until sorted
Stop

5️⃣ Pseudocode ⭐⭐

6️⃣ Selection Sort Program (C++) ⭐⭐

#include <iostream>
using namespace std;

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = 5;

for(int i = 0; i < n-1; i++) {
int minIndex = i;
for(int j = i+1; j < n; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}

for(int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}

#include <iostream>

using namespace std;

int main() {

int arr[] = {64, 25, 12, 22, 11};

int n = 5;

for(int i = 0; i < n-1; i++) {

int minIndex = i;

for(int j = i+1; j < n; j++) {

if(arr[j] < arr[minIndex]) {

minIndex = j;

}

swap(arr[i], arr[minIndex]);

}

for(int i = 0; i < n; i++) {

cout << arr[i] << " ";

}

return 0;

}

Output

7️⃣ Time Complexity of Selection Sort ⭐⭐⭐

🔹 Comparisons

⏱ Time Complexity Table

Case	Time Complexity
Best Case	O(n²)
Average Case	O(n²)
Worst Case	O(n²)

📌 Selection Sort always does the same number of comparisons.

8️⃣ Space Complexity ⭐⭐

Metric	Value
Extra Space	O(1)
Type	In-place sorting

9️⃣ Advantages of Selection Sort ⭐⭐

✔ Simple to understand
✔ Minimum number of swaps
✔ In-place algorithm
✔ Useful when memory writes are costly

🔟 Disadvantages of Selection Sort ⭐⭐

❌ Very slow for large datasets
❌ Always O(n²)
❌ Not adaptive
❌ Not stable (by default)

1️⃣1️⃣ Selection Sort vs Bubble Sort ⭐⭐⭐

Feature	Selection Sort	Bubble Sort
Swaps	Fewer	More
Comparisons	Same	Same
Best Case	O(n²)	O(n) (optimized)
Stability	❌ No	✅ Yes
Learning	Easy	Easy

📌 Exam / Interview Questions (Selection Sort)

Q1. Why is Selection Sort called Selection Sort?
👉 It selects the smallest element each pass

Q2. Is Selection Sort stable?
👉 No (by default)

Q3. Is Selection Sort adaptive?
👉 No

Q4. When is Selection Sort preferred?
👉 When swap cost is high

✅ Summary

✔ Selection Sort selects minimum element
✔ One element fixed per pass
✔ Easy but inefficient
✔ Time Complexity: O(n²)
✔ Space Complexity: O(1)
✔ Good for learning & exams

DSA Selection Sort