Selection Sort

Problem

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

Examples:

Example 1:
Input: arr = [64, 25, 12, 22, 11]
Output: [11, 12, 22, 25, 64]
Explanation: The algorithm repeatedly finds the minimum element and puts it at the beginning.

Example 2:
Input: arr = [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]
Explanation: The algorithm sorts the array by selecting the minimum element in each pass.

Solution

Intuition

  • Selection Sort divides the input array into two parts: a sorted subarray and an unsorted subarray.
  • Initially, the sorted subarray is empty and the unsorted subarray is the entire input array.
  • The algorithm repeatedly selects the smallest element from the unsorted subarray and moves it to the end of the sorted subarray.
  • This process continues until the entire array is sorted.

Approach

  • Find the minimum element in the unsorted array.
  • Swap it with the first element of the unsorted part.
  • Move the boundary between the sorted and unsorted subarrays one element to the right.
  • Repeat until the entire array is sorted.

Complexity Analysis

  • Time Complexity: O(n²) for all cases (best, average, and worst) because the algorithm always makes n(n-1)/2 comparisons.
  • Space Complexity: O(1) as it only requires a single additional memory space for the temporary variable used in swapping.
Implementation
CPP
Run your code to see output here