Understanding Selection Sort: A Simple Sorting Algorithm

Sorting algorithms are the backbone of many programming applications, and Selection Sort is one of the easiest to understand. If you're diving into algorithms for the first time, this one is a great place to start.

In this blog, we'll break down the Selection Sort algorithm step by step, so even beginners can master it!

What is Selection Sort?

Selection Sort is a sorting algorithm that divides an array into two sections:

1. Sorted Section: Starts empty and grows as the algorithm progresses.

2. Unsorted Section: Shrinks as elements are moved to the sorted section.

How it works:

• The algorithm repeatedly selects the smallest (or largest) element from the unsorted section and places it at the correct position in the sorted section.

How Does It Work?

Let's consider an array: [64, 25, 12, 22, 11].

Steps of Selection Sort:

1. Find the Minimum Element: Search through the array and find the smallest number (11).

2. Swap: Swap the smallest number with the first element of the unsorted section.

   • After the first pass: [11, 25, 12, 22, 64].

3. Repeat: Continue this process for the remaining unsorted elements until the entire array is sorted.

Selection Sort Algorithm

Time Complexity:

• Best Case: O(n²)

• Worst Case: O(n²)

• It's not the most efficient algorithm, but it's simple and great for learning.

Space Complexity:

• O(1), as Selection Sort is an in-place sorting algorithm.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find the index of the smallest element in the unsorted section
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap the found minimum element with the first element of the unsorted section
        arr[i], arr[min_index] = arr[min_index], arr[i]
        print(f"Step {i + 1}: {arr}")  # Debugging step to show progress

# Example Usage
arr = [64, 25, 12, 22, 11]
print("Original Array:", arr)
selection_sort(arr)
print("Sorted Array:", arr)

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

Step 1: [11, 25, 12, 22, 64]

Step 2: [11, 12, 25, 22, 64]

Step 3: [11, 12, 22, 25, 64]

Step 4: [11, 12, 22, 25, 64]

Step 5: [11, 12, 22, 25, 64]

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

Visualizing Selection Sort

Imagine you're sorting a deck of cards:

• Look through the deck to find the smallest card and place it in its correct position.

• Repeat this until the entire deck is sorted.

Selection Sort does exactly this, but with arrays instead of cards!

Why Learn Selection Sort?

✅ Easy to Implement: Perfect for beginners learning sorting algorithms.
✅ No Extra Memory Needed: Works directly on the input array.
✅ Foundation for Advanced Concepts: Understanding this will help in mastering more complex algorithms.

Key Takeaways

• Selection Sort is simple but not the most efficient for large datasets.

• It’s an excellent first step in understanding sorting algorithms and their mechanics.