Selection Sort: Concept, Code & Comparison

on




Selection Sort: Concept, Code & Comparison

After learning Bubble Sort, let’s move to another fundamental sorting algorithm — Selection Sort.
It’s slightly more efficient in terms of the number of swaps and helps you understand how “selection” works in algorithms.

What is Selection Sort?

Selection Sort works by repeatedly finding the smallest element from the unsorted part of the list and placing it at the beginning.

It divides the array into two parts:

  • The sorted part (left side)

  • The unsorted part (right side)

Each iteration selects the minimum element from the unsorted list and swaps it into the correct position.

 Step-by-Step Walkthrough

Let’s sort this array:
[64, 25, 12, 22, 11]

Pass 1:
Find the smallest element → 11
Swap with the first → [11, 25, 12, 22, 64]

Pass 2:
Next smallest → 12
Swap with 2nd → [11, 12, 25, 22, 64]

Pass 3:
Next smallest → 22
Swap with 3rd → [11, 12, 22, 25, 64]

Pass 4:
Next smallest → 25 (already in place)

 Final Sorted Output: [11, 12, 22, 25, 64]

 Python Code Implementation

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]

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

Output:

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

⚙️ Time & Space Complexity

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

Space Complexity: O(1) (In-place sorting)

Bubble Sort vs Selection Sort

Feature Bubble Sort Selection Sort
Comparisons O(n²) O(n²)
Swaps Up to O(n²) O(n)
Adaptive Yes (can stop early) No
Stable Yes No (in standard form)
Simplicity Easy Easy
Speed on small datasets Slightly slower Slightly faster

 Key Characteristics

 * Easy to understand
 * Reduces the number of swaps compared to Bubble Sort
 * Still inefficient for large datasets
 * Good for learning the concept of selection and position fixing

Real-Life Analogy

Imagine organizing books on a shelf by height.
You repeatedly look through the remaining unsorted books, find the shortest one, and place it at the start.
That’s Selection Sort — always selecting the smallest and fixing it in order.

Summary

Feature Description
Algorithm Type Comparison-based
Technique Selection
Stable  No
In-place  Yes
Time Complexity O(n²)
Space Complexity O(1)
Best For Teaching and understanding basic sorting logic

Conclusion

While Selection Sort is not the fastest algorithm, it’s a cornerstone concept that helps build your understanding of sorting logic.
By mastering Bubble and Selection Sort, you prepare yourself for advanced algorithms like Merge Sort, Quick Sort, and Heap Sort.



Comments

Post a Comment