📘 Selection Sort

1️⃣ Introduction

Selection Sort is a simple comparison-based sorting algorithm.

🔹 Idea

It works by:

Repeatedly selecting the smallest element
Placing it at its correct position

At each step, it selects the minimum element from the unsorted part.

2️⃣ Working Principle

Divide array into:
- Sorted part (initially empty)
- Unsorted part
Find minimum element in unsorted part
Swap it with the first element of unsorted part
Move boundary of sorted part forward

3️⃣ Algorithm (Selection Sort)

🔹 Pseudocode

SelectionSort(A, n):
   for i = 0 to n-2:
       min_index = i

       for j = i+1 to n-1:
           if A[j] < A[min_index]:
               min_index = j

       swap A[i] and A[min_index]

4️⃣ Example (Step-by-Step)

🔹 Given Array:

A = [64, 25, 12, 22, 11]

🔹 Pass 1 (i = 0)

Find minimum → 11
Swap with 64

[11, 25, 12, 22, 64]

🔹 Pass 2 (i = 1)

Find minimum → 12
Swap with 25

[11, 12, 25, 22, 64]

🔹 Pass 3 (i = 2)

Find minimum → 22
Swap with 25

[11, 12, 22, 25, 64]

🔹 Pass 4 (i = 3)

Find minimum → 25
Already in correct position

[11, 12, 22, 25, 64]

✔ Final Sorted Array

5️⃣ Time Complexity

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

👉 Number of comparisons is always same.

6️⃣ Space Complexity

O(1) (in-place sorting)
No extra memory required

7️⃣ Characteristics of Selection Sort

✔ Simple and easy to understand
✔ In-place algorithm
✔ Performs minimum number of swaps
✖ Not stable (by default)
✖ Not adaptive

8️⃣ Advantages

Requires less memory
Performs fewer swaps
Easy to implement

9️⃣ Disadvantages

Inefficient for large datasets
Always takes O(n²) time
Does not adapt to sorted data

🔟 Comparison with Insertion Sort

Feature	Selection Sort	Insertion Sort
Time Complexity	O(n²)	O(n²)
Best Case	O(n²)	O(n)
Swaps	Minimum	More
Adaptive	No	Yes
Stability	No	Yes

🔚 Conclusion

Selection Sort is a simple sorting algorithm that repeatedly selects the minimum element and places it in the correct position.

It is easy to understand but inefficient for large datasets due to its fixed O(n²) complexity.

📌 Exam Tip

👉 Always include:

Algorithm
Step-by-step example
Time complexity table

selection sort