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:
- Initialization: Start with the entire list as the unsorted section.
- Selection: Scan the unsorted section for the smallest (or largest) item.
- Swapping: Swap this item with the first element of the unsorted section.
- Updating Boundaries: Mark the leftmost unsorted element as sorted, increasing the sorted portion by one.
- 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:
- 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]
- Find minimum in unsorted array
- 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]
- Find minimum in unsorted array
- 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]
- Find minimum in unsorted array
- 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]
- Find minimum in unsorted array
- 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]
- Find minimum in unsorted array
- 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]
- Find minimum in unsorted array
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 byi
.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, updatingmin_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.