DEV Community

Dumb Down Demistifying Dev
Dumb Down Demistifying Dev

Posted on • Updated on

Selection Sort

What do we understand about Selection Sort?

  • Pretty simple once we understand the concept.
  • Mutates original Array rather than returning a new Array
  • Similar to Bubble Sort
  • Both use 2 for-loops and also does the same standard swapping logic
    • Outer loop holds the index pointer of the "smallest" comparison value
    • Inner loop searches for a smaller value than the current "smallest" pointer value
  • Get new smallest value's index
  • Swap in the outer loop by index of new smallest value with current "smallest" pointer value.
  • Time Complexity:
    • Best : O(n^2)
    • Average: O(n^2)
    • Worst : O(n^2)
  • Space Complexity:
    • O(1)
    function SelectionSort(arr) {
        const arrayLength = arr.length;

        for (let i = 0; i < arrayLength - 1; i++) {
            let smallestIndexPointer = i;
            for (let j = i + 1; j < arrayLength; j++) {
                if (arr[j] < arr[smallestIndexPointer]>) {
                    smallestIndexPointer = j;
                }
            }
            if (smallestIndexPointer !== i) {
                [arr[i], arr[smallestIndexPointer]] = [arr[smallestIndexPointer], arr[i]];
            }
        }

        return arr;
    }
Enter fullscreen mode Exit fullscreen mode

Discussion (0)