Understand Selection Sort with Clear Visualizations

Selection Sort is a comparison-based sorting algorithm that divides the input list into two parts: a sorted subset at the beginning of the list and an unsorted subset that occupies the remainder of the list. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted subset, swapping it with the leftmost unsorted element, and moving the boundary of the sorted subset one element to the right.

How The Selection Sort Algorithm Works

Here’s a step-by-step breakdown of how Selection Sort operates:

1. Initialization: Start with the entire list as the unsorted section.
2. Selection: Scan the unsorted section for the smallest (or largest) item.
3. Swapping: Swap this item with the first element of the unsorted section.
4. Updating Boundaries: Mark the leftmost unsorted element as sorted, increasing the sorted portion by one.
5. Repeat: Continue this process until the unsorted section is depleted and the entire array is sorted.

Illustrative Example

Sorting the array [7, 1, 5, 3, 6, 2, 4] in ascending order using Selection Sort:

1. First Pass:
   • Find minimum in unsorted array [7, 1, 5, 3, 6, 2, 4]: 1
   • Swap with the first element: [1, 7, 5, 3, 6, 2, 4]
2. Second Pass:
   • Find minimum in unsorted array [7, 5, 3, 6, 2, 4]: 2
   • After swapping with first element in the unsorted subarray (7): [1, 2, 5, 3, 6, 7, 4]
3. Third Pass:
   • Find minimum in unsorted array [5, 3, 6, 7, 4]: 3
   • After swapping with first element in the unsorted subarray (5): [1, 2, 3, 5, 6, 7, 4]
4. Fourth Pass:
   • Find minimum in unsorted array [5, 6, 7, 4]: 4
   • After swapping with first element in the unsorted subarray (5): [1, 2, 3, 4, 6, 7, 5]
5. Fifth Pass:
   • Find minimum in unsorted array [6, 7, 5]: 5
   • After swapping with first element in the unsorted subarray (6): [1, 2, 3, 4, 5, 7, 6]
6. Sixth Pass:
   • Find minimum in unsorted array [7, 6]: 6
   • After swapping with first element in the unsorted subarray (7): [1, 2, 3, 4, 5, 6, 7]

After these steps, the array is completely sorted in ascending order.

Implementation

def selection_sort(arr):
    # Traverse through all array elements
    for i in range(len(arr)):
        # Find the minimum element in the remaining unsorted array
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j

        # Swap the found minimum element with the first element of the unsorted part
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr

In the Python implementation of Selection Sort, we navigate and sort the array using three key variables: i, min_idx, and j. Each plays a pivotal role in the algorithm’s logic:

• i: Marks the current position within the array that we’re looking to fill with the correctly sorted element. It acts as the index for the outer loop, gradually moving forward as we find and place each minimum element in its correct position.
• min_idx: Holds the index of the smallest (or largest, for descending order) unsorted element found during the current iteration. It’s determined by scanning the unsorted portion of the array in the inner loop. Once identified, this element will be swapped into the position marked by i.
• j: (curr in the animation) Used within the inner loop to traverse the unsorted portion of the array. It compares each element against the current known minimum, updating min_idx whenever a smaller element is found.

Time and Space Complexity of Selection Sort

Aspect	Complexity
Time Complexity	O(n^2)
– Best Case	O(n^2)
– Average Case	O(n^2)
– Worst Case	O(n^2)
Memory Complexity	O(1)

Time Complexity: Selection Sort is known for its straightforward approach, sorting an array by repeatedly finding the minimum element and moving it to the beginning. This process, however, leads to a runtime complexity of O(n^2), where n represents the number of elements in the array. Let’s break down this complexity in simpler terms:

Initially, the algorithm looks at all n elements. After placing the first element in its correct position, it only needs to look through the remaining n-1 elements, then n-2, and so on, down to the last 2 elements.

If you add up all the comparisons n + (n-1) + (n-2) + … + 2 + 1, it sums up to a total of \frac{n(n+1)}{2}. In Big O notation, this is expressed as O(n^2). This quadratic time complexity makes it less efficient for large datasets compared to more advanced algorithms like QuickSort or MergeSort.

Space Complexity: O(1), indicating that it requires a constant amount of additional memory space, which makes it a memory-efficient choice.

Closing Words

Selection Sort stands out for its simplicity and educational value, offering a foundational understanding of sorting algorithms. While it may not be the choice for performance-critical applications, it plays a crucial role in teaching algorithmic thinking and problem-solving strategies.