# Selection Sort

## This blog covers:

* Introduction
    
* Step-by-step working of Selection Sort
    
* Dry Run (Example)
    
* Code Implementation (in Python)
    
* Optimizations
    
* Merits
    
* Demerits
    

---

# 🔄 Selection Sort – A Step-by-Step Guide for Beginners

Sorting is one of the most essential techniques in computer science, and **Selection Sort** is another beginner-friendly algorithm often taught after Bubble Sort. It’s not the most efficient for large datasets but provides a clear understanding of how selection and swapping work.

In this blog, we’ll break down Selection Sort step-by-step with examples, code, optimization tips, and its merits/demerits — all in simple language.

---

## 📘 What is Selection Sort?

Selection Sort is a **comparison-based sorting algorithm**. It works by repeatedly selecting the smallest (or largest) element from the unsorted part of the array and placing it in its correct position.

Think of it like picking the smallest card from a shuffled deck and putting it at the beginning — and repeating until the deck is sorted.

---

## 🔍 Step-by-Step Working of Selection Sort

Let’s sort an array in ascending order using Selection Sort:

Example:

```python
array = [64, 25, 12, 22, 11]
```

🔄 **Step 1: Divide into two parts**

* Left part = Sorted
    
* Right part = Unsorted
    

Initially, the whole array is unsorted.

🔁 **Step 2: Find Minimum**  
From the unsorted part, find the smallest element.

🔁 **Step 3: Swap**  
Swap it with the first element of the unsorted part.

✅ **Step 4: Repeat**  
Move the boundary between sorted and unsorted by one position, and repeat until the array is sorted.

---

## 🧠 Dry Run (Example)

Array = `[64, 25, 12, 22, 11]`

* **Pass 1:**  
    Find min in `[64, 25, 12, 22, 11]` → **11**  
    Swap 11 with 64 → `[11, 25, 12, 22, 64]`
    
* **Pass 2:**  
    Find min in `[25, 12, 22, 64]` → **12**  
    Swap 12 with 25 → `[11, 12, 25, 22, 64]`
    
* **Pass 3:**  
    Find min in `[25, 22, 64]` → **22**  
    Swap 22 with 25 → `[11, 12, 22, 25, 64]`
    
* **Pass 4:**  
    Find min in `[25, 64]` → **25**  
    Already in correct place → `[11, 12, 22, 25, 64]`
    

✅ Array is sorted!

---

## 💻 Python Code – Selection Sort

```python
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Example usage
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)
```

**Output:**

```python
Sorted array: [11, 12, 22, 25, 64]
```

---

## ⚙️ Optimizations

While Selection Sort always makes **O(n²) comparisons**, we can reduce unnecessary swaps:

* Instead of swapping at every comparison, swap only **once per pass** (when the minimum is found).
    
* This reduces the number of swaps drastically compared to Bubble Sort.
    

---

## ✅ Merits of Selection Sort

| Merit | Description |
| --- | --- |
| 🔹 Simple | Easy to implement and understand |
| 🔹 In-place | Requires no extra memory |
| 🔹 Fewer swaps | Performs fewer swaps compared to Bubble Sort |
| 🔹 Good for small data | Works fine for small datasets |

---

## ❌ Demerits of Selection Sort

| Demerit | Description |
| --- | --- |
| 🔸 Inefficient | Time complexity O(n²) in all cases |
| 🔸 Not stable | May change the relative order of equal elements |
| 🔸 Poor for large data | Not suitable for large-scale sorting |

---

## 📊 Time and Space Complexity

| Case | Time Complexity |
| --- | --- |
| Best | O(n²) |
| Average | O(n²) |
| Worst | O(n²) |
| Space | O(1) |

---

## 🧾 Final Thoughts

Selection Sort is more efficient in terms of swaps than Bubble Sort, but it still suffers from quadratic time complexity, making it unsuitable for big datasets.

Still, it’s a **must-learn algorithm for beginners** as it introduces the concept of selecting the minimum/maximum element and placing it in the right position.

Once you’re comfortable with Selection Sort, move on to faster algorithms like:

* Insertion Sort
    
* Merge Sort
    
* Quick Sort