Selection Sort

Selection Sort is a simple comparison-based sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the array and moving it to the sorted portion. While Selection Sort is intuitive and easy to implement, it is generally inefficient on large lists due to its O(n²) time complexity.

Selection Sort: The Basics

Selection Sort sorts an array by:

1. Dividing the array into a sorted and an unsorted portion.
2. Finding the smallest element in the unsorted portion and swapping it with the first element of the unsorted portion.
3. Moving the boundary between the sorted and unsorted portions by one element after each iteration.
4. Repeat the process until the entire array is sorted.

Time Complexity: - Worst, Average, and Best Case: O(n²), because each element is compared with every other element in the unsorted portion, regardless of the initial order.

Space Complexity: O(1), since Selection Sort performs sorting in-place and does not require additional memory.

Stability: Selection Sort is not stable by default. Equal elements might be swapped in a way that disrupts their original order.

Selection Sort Algorithm Steps

1. Outer Loop: Runs from the first to the second-to-last element.
2. Inner Loop: Finds the smallest element in the unsorted portion.
3. Swapping: Swaps the found minimum element with the first element of the unsorted portion.
4. Repeat: Moves the boundary of the sorted portion one position to the right.

Code Example: Selection Sort

from typing import List

def selection_sort(arr: List[int]) -> None:
    """
    Perform selection sort on the input array `arr`.
    - arr: List of integers to be sorted (in place)
    """
    n = len(arr)
    for i in range(n):
        # Assume the first element of unsorted portion is the minimum
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j  # Update min_index if a smaller element is found
        # Swap the found minimum element with the first element of the unsorted portion
        arr[i], arr[min_index] = arr[min_index], arr[i]

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

Explanation of Code

Outer Loop:

• i represents the boundary between the sorted and unsorted portions of the array.
• Each pass extends the sorted portion by one element.

Inner Loop:

• Finds the index of the smallest element in the unsorted portion (min_index).
• This element is then swapped with the element at index i, moving the smallest element to its correct position.

Swapping:

• After finding the smallest element, the algorithm swaps it with the first element of the unsorted portion, thus expanding the sorted portion by one element.

Example Execution: For an array [64, 25, 12, 22, 11]: 1. Pass 1: [11, 25, 12, 22, 64] (11 is the smallest element and is moved to the first position) 2. Pass 2: [11, 12, 25, 22, 64] (12 is the smallest in the unsorted portion) 3. Pass 3: [11, 12, 22, 25, 64] (22 is the smallest in the unsorted portion) 4. Pass 4: [11, 12, 22, 25, 64] (Sorted array)