Selection Sort - Typescript

Selection sort is simple and easy to implement. But it is also very inefficient in terms of time complexity.
Time Complexity
  • Best: Ω(n^2)
  • Average: Ω(n^2)
  • Worst: Ω(n^2)
    • In selection sort, we loop through the array by selecting the smallest value and then swapping it to the left side of the array till it is sorted in ascending order.
    Code 
    const selectionSort = (arr: number[]): number[] => {
    const len: number = arr.length;
    let minInd: number = -1;
    for (let i = 0; i < (len - 1); i++) {
        minInd = i

        for (let j = (i + 1); j < len; j++) {
            if (arr[j] < arr[minInd]) {
                minInd = j
            }
        }

        if (minInd !== i) {
            [arr[i], arr[minInd]] = [arr[minInd], arr[i]];
        }
    }
    return arr;
}

const result = selectionSort([64, 25, 12, 22, 11]);
    Output 
    Output: [11, 12, 22, 25, 64]
    Here how the code is working
  • The function takes the unsorted array [64, 25, 12, 22, 11].
  • Iteration 1: [11, 25, 12, 22, 64] → i = 0, minInd = 4 and min value is 11.
  • Iteration 2: [11, 12, 25, 22, 64] → i = 1, minInd = 2 and min value is 12.
  • Iteration 3: [11, 12, 22, 25, 64] → i = 2, minInd = 3 and min value is 22.
  • Iteration 4: [11, 12, 22, 25, 64] → i = 3, minInd = 3 and min value is 25.
  • For iteration 4 it won't swap the value as the minInd and i are the same so there are no unnecessary swap.
    • That’s all for the selection sort, thanks for reading!

    55

    Categories:

    TypescriptJavascript

    Tags:

    TypescriptJavascriptDatastructureProgramming

    This website collects cookies to deliver better user experience

    Selection Sort - Typescript