Selection Sort

Overview#

  • Time Complexity: O(n^2), makes at most O(n) swaps
  • Space Complexity: O(1)
  • In-Place
  • Not stable (If implemented with a linked list, then it is stable)
    • Example: [5,3,3',2,1] -> [1,3,3',2,5] -> [1,2,3',3,5] -> order of 3 and 3' has been swapped

General Idea#

Sorts an array by repeatedly finding the minimum element from the unsorted part of the array and puts it at the beginning. The array maintains two subarrays in an array. The front part of the array is a subarray containing the already sorted elements.

We have an outer loop which runs from 0 to the len(arr) - 1 index. In each iteration, we run an inner loop which searches for the minimum element in the remaning unsorted elements and place it at the next index available at the front subarray. Hence, the inner loop runs from index (i+1) to (len(arr) - 1).

Time Complexity#

As seen from the 2 loops, we have a time complexity of O(n^2).

Space Complexity#

We only maintain temporary variables to know the current minimum element's index. Hence, the space complexity is constant - O(1).

Implementation#

def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
# range starts from index (i+1) as indices (0 to (i-1)) contain sorted elements
for j in range((i+1), len(arr)):
if(arr[min_idx] > arr[j]):
min_idx = j
# swap
temp = arr[min_idx]
arr[min_idx] = arr[i]
arr[i] = temp
return arr
if __name__ == "__main__":
arr = [9,8,7,6,5,4,3,2,1]
print(selection_sort(arr))

Comparison with Bubble Sort#

Selection sort uses a maximum of n swaps whereas in bubble sort, we use up to n swaps for each element - requires up to n^2 swap operations. Since write operations are memory-intensive, selection sort can be more efficient than bubble sort for large lists.

Link: http://codepumpkin.com/selection-sort-algorithms/