Sorting is one of the most important concepts in Data Structures and Algorithms (DSA). It helps organize data in a meaningful order, making searching, processing, and analysis much faster.
Among the simplest sorting algorithms, Selection Sort is widely taught because of its easy-to-understand logic. Instead of repeatedly swapping adjacent elements like Bubble Sort, Selection Sort selects the smallest element from the unsorted portion of the array and places it in its correct position.
In this comprehensive guide, you’ll learn everything about Selection Sort, including its working principle, algorithm, examples, Java implementation, time complexity, advantages, disadvantages, interview questions, and much more.
📚 Table of Contents
- What is Selection Sort?
- Why is it called Selection Sort?
- Real-Life Analogy
- How Selection Sort Works
- Step-by-Step Example
- Selection Sort Algorithm
- Flow of Selection Sort
- Java Program
- Dry Run of the Program
- Time Complexity Analysis
- Space Complexity
- Is Selection Sort Stable?
- Is Selection Sort In-Place?
- Can Selection Sort Be Optimized?
- Advantages
- Disadvantages
- Applications
- Bubble Sort vs Selection Sort vs Insertion Sort
- Frequently Asked Questions
- Conclusion
🎯 What is Selection Sort?
Selection Sort is a simple comparison-based sorting algorithm that repeatedly selects the smallest element from the unsorted portion of the array and places it at the beginning.
After every pass:
- ✅ One smallest element reaches its correct position.
- ✅ The sorted portion grows from left to right.
- ✅ The unsorted portion becomes smaller.
Unlike Bubble Sort, Selection Sort does not compare adjacent elements. Instead, it scans the entire unsorted portion to find the minimum element.
🤔 Why is it Called Selection Sort?
The algorithm repeatedly selects the smallest element from the remaining unsorted elements.
For example,
64 25 12 22 11
During the first pass, it selects 11.
During the second pass, it selects 12.
During the third pass, it selects 22.
Since the algorithm works by selecting the minimum element in every pass, it is called Selection Sort.
🃏 Real-Life Analogy
Imagine five students standing in random order according to their heights.
170 165 180 150 160
Your job is to arrange them from shortest to tallest.
Instead of swapping everyone repeatedly, you:
- Look at everyone.
- Find the shortest student.
- Place them at the first position.
- Repeat the process with the remaining students.
This is exactly how Selection Sort works.
⚙️ How Selection Sort Works
The algorithm performs the following steps:
1️⃣ Assume the first unsorted element is the smallest.
2️⃣ Compare it with every remaining element.
3️⃣ If a smaller element is found, remember its index.
4️⃣ After scanning the entire unsorted portion, swap the smallest element with the first unsorted element.
5️⃣ Repeat until the array is completely sorted.
✨ Step-by-Step Example
Consider the array:
[64, 25, 12, 22, 11]
🔹 Pass 1
Current array
64 25 12 22 11
Find the smallest element.
Smallest = 11
Swap 64 and 11.
11 25 12 22 64
✅ 11 is now fixed.
🔹 Pass 2
Remaining unsorted array
25 12 22 64
Smallest = 12
Swap 25 and 12.
11 12 25 22 64
✅ 12 is fixed.
🔹 Pass 3
Remaining array
25 22 64
Smallest = 22
Swap.
11 12 22 25 64
🔹 Pass 4
Remaining array
25 64
Smallest = 25
Already in the correct position.
Final array
11 12 22 25 64
🎉 Array sorted successfully.
📝 Selection Sort Algorithm
Step 1: Start
Step 2: Assume current element is the minimum.
Step 3: Search the remaining array.
Step 4: Find the smallest element.
Step 5: Swap it with the first unsorted element.
Step 6: Repeat until the array is sorted.
Step 7: Stop.
🔄 Flow of Selection Sort
Start
↓
Assume Current Element is Minimum
↓
Search Remaining Array
↓
Found Smaller Element?
↓
Yes
↓
Update Minimum Index
↓
End of Search?
↓
Swap Minimum with Current Position
↓
Next Pass
↓
Array Sorted
↓
Stop
💻 Java Program
public class SelectionSort {
public static void selectionSort(int arr[]) {
int n = arr.length;
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;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int arr[] = {64,25,12,22,11};
selectionSort(arr);
System.out.println("Sorted Array:");
for(int num : arr)
System.out.print(num + " ");
}
}
🖥 Output
Sorted Array
11 12 22 25 64
🔍 Dry Run
Input
29 10 14 37 13
Pass 1
Minimum = 10
10 29 14 37 13
Pass 2
Minimum = 13
10 13 14 37 29
Pass 3
Minimum = 14
Already in correct position.
10 13 14 37 29
Pass 4
Minimum = 29
10 13 14 29 37
🎉 Sorted.
📈 Time Complexity Analysis
Let’s derive the time complexity mathematically.
Pass 1
The algorithm compares
n - 1
elements.
Pass 2
n - 2
comparisons.
Pass 3
n - 3
comparisons.
…
Last Pass
1
comparison.
Total comparisons
[
(n-1)+(n-2)+(n-3)+\cdots+1
]
Using the formula
[
1+2+3+\cdots+k=\frac{k(k+1)}{2}
]
where
[
k=n-1
]
we get
[
\frac{n(n-1)}{2}
]
Ignoring constants and lower-order terms,
[
O(n^2)
]
🟢 Best Case
Suppose the array is already sorted.
1 2 3 4 5
Even then, Selection Sort still searches the entire unsorted portion to verify that the current element is indeed the smallest.
Therefore,
Best Case = O(n²)
🟡 Average Case
Random array
4 2 5 1 3
The algorithm still performs the same number of comparisons.
Average Case = O(n²)
🔴 Worst Case
Reverse sorted array
5 4 3 2 1
The algorithm again scans the entire unsorted portion in every pass.
Worst Case = O(n²)
💾 Space Complexity
Selection Sort requires only one temporary variable for swapping.
Therefore,
Space Complexity = O(1)
🔄 Number of Swaps
One of the biggest advantages of Selection Sort is that it performs very few swaps.
For an array of n elements,
Maximum swaps =
n − 1
For example,
If
n = 5
Maximum swaps =
4
This is much fewer than Bubble Sort, which may perform many swaps in a single pass.
📌 Is Selection Sort Stable?
❌ No.
Suppose we have
10A 20 10B
After sorting,
10B 10A 20
The relative order of equal elements changes.
Therefore,
Selection Sort is not a stable sorting algorithm.
📌 Is Selection Sort In-Place?
✅ Yes.
It uses only one temporary variable.
Extra memory required is constant.
🚀 Can Selection Sort Be Optimized?
This is one of the most common interview questions.
The Answer
❌ No.
Unlike Bubble Sort, Selection Sort cannot be optimized to improve its best-case time complexity.
Even if the array is already sorted,
1 2 3 4 5
the algorithm must still compare every remaining element to ensure that the current element is the smallest.
Therefore,
- Best Case = O(n²)
- Average Case = O(n²)
- Worst Case = O(n²)
A small coding improvement is to avoid an unnecessary swap when the minimum element is already at the correct position:
if(minIndex != i){
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
This reduces unnecessary swaps but does not change the time complexity.
🌍 Applications of Selection Sort
Selection Sort is mainly used for:
- 🎓 Learning DSA concepts
- 📚 Educational purposes
- 🧪 Small datasets
- 💾 Situations where minimizing the number of swaps is important
It is not recommended for large datasets.
📊 Bubble Sort vs Selection Sort vs Insertion Sort
| Feature | Bubble Sort | Selection Sort | Insertion Sort |
|---|---|---|---|
| Technique | Swap adjacent elements | Select minimum element | Insert element into sorted portion |
| Best Case | O(n²) Normal / O(n) Optimized | O(n²) | O(n) |
| Average Case | O(n²) | O(n²) | O(n²) |
| Worst Case | O(n²) | O(n²) | O(n²) |
| Stable | ✅ Yes | ❌ No | ✅ Yes |
| In-place | ✅ Yes | ✅ Yes | ✅ Yes |
| Maximum Swaps | Many | n − 1 | Few shifts |
❓ Frequently Asked Questions (FAQs)
Q1. Why is it called Selection Sort?
Because it repeatedly selects the smallest element from the unsorted portion of the array.
Q2. Is Selection Sort stable?
No. The relative order of equal elements may change after sorting.
Q3. Is Selection Sort an in-place algorithm?
Yes. It uses only constant extra memory.
Q4. Can Selection Sort be optimized?
No. The algorithm must always search the entire unsorted portion to find the minimum element. Therefore, its time complexity remains O(n²) in all cases.
Q5. How many swaps does Selection Sort perform?
At most n − 1 swaps.
Q6. Why does Selection Sort perform fewer swaps than Bubble Sort?
Because it performs only one swap per pass after finding the minimum element, whereas Bubble Sort may swap adjacent elements multiple times during each pass.
Q7. Which element reaches its correct position after each pass?
The smallest unsorted element reaches its correct position at the beginning of the array.
🎯 Key Takeaways
- 🎯 Selection Sort repeatedly selects the smallest element from the unsorted portion.
- 🔄 After each pass, one element reaches its correct position.
- 📈 Best, Average, and Worst Case Time Complexity = O(n²).
- 💾 Space Complexity = O(1).
- ✅ It is an in-place sorting algorithm.
- ❌ It is not stable.
- 🔁 It performs at most n − 1 swaps.
- 🎓 It is easy to understand and is commonly taught as one of the first sorting algorithms.
🎉 Conclusion
Selection Sort is a straightforward and intuitive sorting algorithm that introduces the concept of finding the minimum element and placing it in its correct position. Although its O(n²) time complexity makes it unsuitable for large datasets, it has one significant advantage: it performs very few swaps, making it useful in scenarios where swapping data is expensive.
Understanding Selection Sort provides a solid foundation for learning more advanced algorithms such as Insertion Sort, Merge Sort, Quick Sort, and Heap Sort. Mastering its working principle also strengthens your understanding of comparison-based sorting techniques, which are frequently discussed in coding interviews and university examinations.
