selection sort example step by step

selection sort example step by step explanation

🎯 What is Selection Sort?

Selection Sort is a simple sorting algorithm that repeatedly selects the smallest element from the unsorted part of the array and places it at the beginning.

---

📌 Definition

Selection Sort is a comparison-based sorting algorithm in which the smallest element is selected from the unsorted portion and swapped with the first unsorted element.

---

🧠 How Selection Sort Works

Steps:

1. Find the smallest element in the array
2. Swap it with the first element
3. Move to next position
4. Repeat for remaining unsorted part
5. Continue until array is sorted

---

📊 Example

Unsorted Array:

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

---

🔁 Pass 1

Smallest = 11

Swap with first element:

[11, 25, 12, 22, 64]

---

🔁 Pass 2

Remaining array: [25, 12, 22, 64]

Smallest = 12

[11, 12, 25, 22, 64]

---

🔁 Pass 3

Remaining array: [25, 22, 64]

Smallest = 22

[11, 12, 22, 25, 64]

---

🔁 Pass 4

Remaining array: [25, 64]

Already in order

[11, 12, 22, 25, 64]

---

📌 Final Sorted Array

[11, 12, 22, 25, 64]

---

💻 Algorithm (Pseudocode)

SelectionSort(A, n)

1. for i = 0 to n-1
2.     minIndex = i
3.     for j = i+1 to n-1
4.         if A[j] < A[minIndex]
5.             minIndex = j
6.     swap(A[i], A[minIndex])

---

🐍 Python Program for Selection Sort

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
arr = [64, 25, 12, 22, 11]

result = selection_sort(arr)

print("Sorted Array:", result)

---

Output:

Sorted Array: [11, 12, 22, 25, 64]

---

⚡ Time Complexity

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

---

📊 Space Complexity

• O(1) (in-place sorting)

---

🆚 Selection Sort vs Bubble Sort

Feature	Selection Sort	Bubble Sort
Method	Select minimum	Swap adjacent
Swaps	Fewer swaps	Many swaps
Speed	Slightly faster	Slower
Stability	❌ Not stable	✅ Stable
Complexity	O(n²)	O(n²)

---

📌 Advantages

• Simple to understand
• Performs fewer swaps than bubble sort
• Works in-place (no extra memory)

---

❌ Disadvantages

• Very slow for large data sets
• Always O(n²) time complexity
• Not stable sorting algorithm

---

🧠 Real Life Example

• Selecting smallest student roll number and placing first 🧑‍🎓
• Sorting cards by repeatedly picking smallest card 🃏

---

📌 Summary

• Selection sort selects the smallest element repeatedly
• Places it at the correct position
• Performs O(n²) comparisons
• Efficient for small datasets only

---

❓ Important Questions

Short Questions

1. What is selection sort?
2. What is the main idea of selection sort?
3. What is time complexity of selection sort?
4. Is selection sort stable?
5. How many swaps are used in selection sort?

---

Long Questions

1. Explain selection sort with example.
2. Write algorithm of selection sort.
3. Write Python program for selection sort.
4. Compare selection and bubble sort.
5. Explain advantages and disadvantages of selection sort.