Explanation

• Concept: Selection sort is a simple in-place comparison-based sorting algorithm that divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted.
• Process: Selection sort repeatedly selects the minimum element from the unsorted portion and swaps it with the leftmost unsorted element.
• Steps:
  • Find the minimum element in the unsorted portion of the list.
  • Swap the minimum element with the leftmost unsorted element.
  • Move the subarray boundary one element to the right.
  • Repeat this process until the entire list is sorted.
• Efficiency: Selection sort has a time complexity of O(n^2) for the worst and average cases, making it inefficient for large datasets. However, it has a simple implementation and requires only O(1) additional memory space.

Algorithm Recap

• Loop: Iterate through the list, selecting the minimum element from the unsorted portion.
• • Find the minimum element in the unsorted portion.
  • Swap the minimum element with the leftmost unsorted element.
  • Move the subarray boundary one element to the right.
• Endcondition: When the entire list is sorted, the algorithm terminates.

Considerations

• Selection sort is inefficient for large datasets due to its O(n^2) time complexity.
• It is not stable, meaning it may change the relative order of equal elements.
• Selection sort is simple to implement and requires only O(1) additional memory space.

Complexity Analysis

• Time: O(n^2) because in the worst case, every element may need to be compared with every other element.
• Space:

  O(1), as no additional data structures are used.

  • Uses O(1) space, as it only requires a few variables without allocating additional data structures.

Python Implementation

      
          from typing import List

def selection_sort(arr: List[int]) -> List[int]:
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

def run_algo():
    arr = [int(x) for x in input("Enter array (space separated): ").split()]
    sorted_arr = selection_sort(arr)
    print("Sorted array:", sorted_arr)

if __name__ == "__main__":
    run_algo()

        

Test Cases

• Random Order

  Input:

  • Array: [64, 25, 12, 22, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 12, 22, 11] is sorted in ascending order.

• Already Sorted

  Input:

  • Array: [11, 12, 22, 25, 64]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array is already sorted, so the output remains the same.

• Reverse Order

  Input:

  • Array: [64, 25, 22, 12, 11]
  • Target:

  Expected Output: [11, 12, 22, 25, 64]

  Explanation: The input array [64, 25, 22, 12, 11] is sorted in ascending order.

• Single Element

  Input:

  • Array: [42]
  • Target:

  Expected Output: [42]

  Explanation: A single element array is already sorted.

• Empty Array

  Input:

  • Array: []
  • Target:

  Expected Output: []

  Explanation: An empty array remains empty after sorting.

Python Test Cases Implementation

          def run_tests():
    tests = [
        {"input": [64, 25, 12, 22, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [11, 12, 22, 25, 64], "expected": [11 ,12, 22, 25, 64]},
        {"input": [64, 25, 22, 12, 11], "expected": [11, 12, 22, 25, 64]},
        {"input": [42], "expected": [42]},
        {"input": [], "expected": []},
    ]
    for i, test in enumerate(tests, 1):
        result = selection_sort(test["input"])
        assert result == test["expected"], f"Test {i} failed: Expected {test['expected']}, got {result}"
        print(f"Test {i} passed.")
if __name__ == "__main__":
    run_tests()

        

Usage and Applications