Selection sort

Cover photo from: Unsplash

Intro

This post is a part of a sorting series, where we go over each sorting methods from bubble sort to radix sort, and I will give you some simple explanation. The importance of sorting can be measured by the success of Google search engine vs other search engines. At the end of the day, it gives you the most useful results - based on its well designed sorting algo.

Selection sort

Selection sort basically a very easy method, and can be imagined and implemented in the same way. The main logic is the following:

1. Take an unsorted array of elements
2. Create a new array - for ex. starting from the left, initially [] - this will be your sorted sublist
3. Your input will be your second, unsorted sublist
4. Find the smallest - or largest - element of your unsorted sublist - depending on your preferences
5. Insert that into your sorted sublist - at the end
6. Move the boundaries

 Visual demo

Performance and complexity

Sadly, this is an easy solution but it costs you some memory and computation power, and I will show you this through an example.

Example

Let say, your starting element is in const array = [ 4, 1, 3, 9];, in where the length of your array is n = 4;

You have to find the smallest element of this list, which requires n - 1 comparisons. Finding the next one requires n - 2 and so on. On large lists, this soon become quadratic - known as O(n²).

When to use?

If you have small lists - and you are aware and you manage the length of your input, you can use this. In this situation, it can be helpful because of its simplicity.

Implementation

function selectionSort(array) {

// break the reference
  const elements = [...array];
  for (let i = 0; i < elements.length; i++) {

// assume that the 'first` is the smallest
    let smallestIndex = i;

// find the smallest index
    for(let j = i + 1; j < elements.length; j++) if(elements[j] < elements[smallestIndex]) smallestIndex = j;

// if the index is not the same, swap the two numbers
    if(smallestIndex !== i) [elements[i], elements[smallestIndex]] = [elements[smallestIndex], elements[i]]
  }

  return elements;
}

Demo

You can check out this demo page, which is fancy enough to give you a nice understanding.

Visualgo

Thanks four your time :)