- Time Complexity:
O(n^2), makes at most
- Space Complexity:
- 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
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
(len(arr) - 1).
As seen from the 2 loops, we have a time complexity of
We only maintain temporary variables to know the current minimum element's index. Hence, the space complexity is constant -
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.