Selection sort | Chinese Rule of Eight

https://en.wikipedia.org/wiki/Selection_sort

Worst-case performance О(n2) comparisons, О(n) swaps
Best-case performance О(n2) comparisons, О(n) swaps

The idea is that we latch onto the first element and deem it being the minimum.
We then go through the rest of the array, and look for anything that is smaller. If so, we swap. This is 1 pass.

At this point, after the 1st pass, we deem first element as minimum. Then we move on
to the next element and call it the minimum. We do another pass and look in the leftover array
to see if there’s anything smaller than our minimum. If so, swap.

We keep doing this, pulling minimum numbers from the array and pushing it towards the front, until
all the elements are sorted from smallest to largest.

So there’s 2 loops: outer and inner.

Outer simply goes through the array.

The inner goes through the remaining elements AFTER the outer via a loop and compares it to the outer.

if the inner element is smaller than the outer element, then we swap. Essentially what is happening is that we are bringing in the smallest element to the front.

Example

1	var dataArray = [8,3,1, 6, 2];

Given an array, we make passes on it where:

– we select the starting value to be the minimum.
– we then make (length of array – 1) passes over it. (through all of our passes, the last element will be automatically sorted, so no need to do anything on it)
– For every pass, we need to do the very important action of pulling the minimum from the array and swapping it with the first value.

Example

Outer starts at index 0, which is value 6 .

[6] 8 0 7 6 4 3 1 5 10

Inner starts at the next element at value 8.

8 < 6? no

0 < 6? yes. swap

[0] 8 6 7 6 4 3 1 5 10

7 < 0? no

6 < 0? no

4 < 0? no

3 < 0? no

1 < 0? no

5 < 0? no

10 < 0? no.

outer 0 is finished.

0 [8] 6 7 6 4 3 1 5 10

outer 2. minimum starts at index 1, which is value 8.

Inner starts at next element, which is value 6.

6 < 8? yes. swap

0 [6] 8 7 6 4 3 1 5 10

7 < 6? no

6 < 6? no

4 < 6? yes, swap.

0 [4] 8 7 6 6 3 1 5 10

3 < 4? yes, swap

0 [3] 8 7 6 6 4 1 5 10

1 < 3? yes, swap

0 [1] 8 7 6 6 4 3 5 10

5 < 1? no

10 < 1? no.

Outer index 1 finished.

Outer index 2 starts, which is value 8.

0 1 [8] 7 6 6 4 3 5 10

…continuing on in the same fashion…

Eventually all the smallest number will be swapped to the front, resulting in the list being sorted.

full source

"use strict";

// GIVEN

// E A D H B

// first pass looks for the minimal value, and swaps it with the value at the front of the list

// A E D H B

// next pass finds the minimal value after the first element (which is now in place) and swaps it.

// so from e, d, h, b..b is smallest and swap with the next value, which is e.

// A B D H E

// move on, and do another pass , D, H, E.

// D is smallest so everything stays

// A B D H E

// move on, and do another pass. H, E.

// E is smaller is swap H and E.

// A B D E H

var dataArray = [8,3,1,6,2];

function swap(array, index1, index2) {

var temp = array[index1];

array[index1] = array[index2];

array[index2] = temp;

}

// given a certain pass

// we get the minimum value and swap it

function swapSmallerValuesToFront(data, outerIndex, lastIndex) {

for (var innerIndex = outerIndex + 1; innerIndex <= lastIndex; innerIndex++) {

console.log("");

console.log("inner index: " + innerIndex + ", data[inner]: " + data[innerIndex]);

console.log("data[outerIndex]: " + data[outerIndex]);

if (data[innerIndex] < data[outerIndex]) {

console.log(" We need to swap because current element is smaller");

swap(data, innerIndex, outerIndex);

console.log("---> data display: " + data);

}

function selectionSort(intArray) {

var data = intArray.slice(0);

var indexOfMinValue, temp;

var lastIndex = data.length-1;

// we always do length - 1 passes

for (var pass = 0; pass <= lastIndex - 1; pass++) {

console.log("---------------> Outer Index: " + pass + " <-----------");

swapSmallerValuesToFront(data, pass, lastIndex);

}

return data;

}

let sortedArray = selectionSort(dataArray);

console.log(sortedArray);