SelectionSort
Description
Search for the smallest number, swap it into the first index. Going onwards, look for 2nd smallest number and swap with 2nd index. Repeat this process.
Complexity Analysis
Average case | \( O(n^2) \) |
|---|---|
Best case | \( O(n^2) \) |
Worst case | \( O(n^2) \) |
Space Complexity | \( O(1) \) |
def selectionSort(arr):
for i in range(len(arr)):
minElem = arr[i]
minIdx = i
# Loop through remaining array for a smaller element than current, then swap
for j in range(i+1, len(arr)):
if arr[j] < minElem:
minElem = arr[j]
minIdx = j
arr[i], arr[minIdx] = arr[minIdx], arr[i]
return arrGeoffrey Lee