DEV Community

Cover image for Selection Sort - Typescript
Manthan Bhatt
Manthan Bhatt

Posted on

Selection Sort - Typescript

#typescript #javascript #datastructure #programming

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.

Selection Sort

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]);
Enter fullscreen mode Exit fullscreen mode

Output 

Output: [11, 12, 22, 25, 64]
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (1)

Collapse
 
aminnairi profile image
Amin • • Edited

Maybe you could use relevant variables names with more than one character, this way complete beginners (we all have been there) can learn from your post some valuable knowledges and you target a larger audience.

Here is a proposal for you and others to better grasp the algorithm behind the selection sort.

const selectionSort = (numbers: number[]): number[] => {
  const {length} = numbers;

  for (let first = 0; first < (length - 1); first++) {
    let lowest = first;

    for (let second = (first + 1); second < length; second++) {
      if (numbers[second] < numbers[lowest]) {
        lowest = second;
      }
    }

    if (lowest !== first) {
      [numbers[first], numbers[lowest]] = [numbers[lowest], numbers[first]];
    }
  }

  return numbers;
}

const result = selectionSort([64, 25, 12, 22, 11]);

console.log(result);
Enter fullscreen mode Exit fullscreen mode

Read next

abhay_yt_52a8e72b213be229 profile image

Implementing Route Guards in React: Protecting Your Routes with Authentication and Roles

Abhay Singh Kathayat -

abhay_yt_52a8e72b213be229 profile image

Mastering MobX: Simplified and Reactive State Management for React

Abhay Singh Kathayat -

abhay_yt_52a8e72b213be229 profile image

Controlled vs Uncontrolled Components in React: Choosing the Right Approach

Abhay Singh Kathayat -

abhay_yt_52a8e72b213be229 profile image

React.js Explained: A Comprehensive Guide to Building Modern Web Applications

Abhay Singh Kathayat -