September 10, 2018 ·

# Sorting algorithms explained

Today we are going to go deeper into sorting algorithms to see the number of times they run to complete their cycle and also explore stability.

What is an Algorithm?
A process or set of rules to be followed in calculations or a set of problems. - solving operations, especially by a computer.

For this exercise, we are going to compare Sorting algorithms.

Bubble sort
This one is easy to understand, and that's why bubble sort is recommended for beginners.

For bubble sort algorithm we use do/while loop (probably you will never use it in production because it is not effective compared to other solutions.

Gist example

``````let numbers = [10,5,3,8,2,6,4,7,9,1];
// lets sort it with bubble sort, first we create a function
const swapper = (numbers) => {
// to acumulate number of iterations
var iterations = 0;
do {
// if swapping is set to false, this will be the last time do run
var swapped = false;
// lets use i to add logic to our sorting algorithm
for (let i = 0; i < numbers.length; i++) {
// we want to sort from less than greater numbers so ->
if (numbers[i] > numbers[i+1]) { // 10 > 8 then
// we save our first number in an acumulator variable
var temp = numbers[i]; // 10
// swap the first number for the secnd
numbers[i] = numbers[i+1]; // change 10 for 8 in first loop
// swap second number for first number
numbers[i+1] = temp; // change 8 for 10 in first loop
// it swapped, lets do other iteration
swapped = true;
console.log(numbers);
// we want to know the number of iterations used to solve the sorting
console.log("iterations: "+ iterations++);
}
}
} while (swapped);
}
swapper(numbers);
// iterations: 25
``````

Insertion sort
It's called insertionSort because we use splice to insert into the array when sorting.
Gist example Insertion sort

``````let nums = [10,5,3,8,2,6,4,7,9,1];
let insertionSort = nums => {
let iterations = 0;
// for each number starting on 2nd slot
for (let i = 1; i < nums.length; i++) {
//console.log("outer loop: " + nums[i]); // 5 (second number of array)
for (let j = 0; j < i; j++) {
//console.log("inner loop: " + nums[j]); // 10
if (nums[i] < nums[j]) { // if 5 is less than 10
// get one element from slot i (take from array, array gets modified)
let spliced = nums.splice(i, 1);
//insert spliced in slot j, and displace array (if replace 0 for 1 slot 0 gets replaced instead of displaced)
nums.splice(j, 0, spliced);
console.log("spliced: " + nums);
console.log("number of iterations: "+ ++iterations)
}
}
}
};
insertionSort(nums);
// number of iterations to sort: 9
``````

The number of iterations got cut by half, neat!

Merge sort
Merge sort is the Algorithm most engines use when you run array.sort();
What merge sort does, is split array into 2 parts, then split those 2 arrays in 2, now we have 4 arrays, when the arrays can no longer be split in half, the algorithm starts to merge the numbers in order.

Merge sort algorithm is very stable because it does not move indexes if the numbers do get repeated.
Code example Merge sort

``````let nums = [10,5,3,8,2,6,4,7,9,1];
var iterations = 0;
const mergeSort = (nums) => {
++iterations;
console.log(iterations);
if(nums.length < 2) {
return nums;
}

const length = nums.length;
const middle = Math.floor(length / 2);
const left = nums.slice(0, middle); //left part of the array
const right = nums.slice(middle, length);

const sortedLeft = mergeSort(left);
const sortedRight = mergeSort(right);
return stitch(sortedLeft, sortedRight);
}

const stitch = (left, right) => {
const results = [];
while(left.length && right.length) {
if (left <= right) {
results.push(left.shift());
} else {
results.push(right.shift());
}
}
while(left.length) {
results.push(left.shift());
}
while(right.length) {
results.push(right.shift());
}
return results;
}

let result = mergeSort(nums);
console.log(result);
``````

This representation of algorithms is for informational purposes; you should not use them in production, I recommend you use array.sort() native function for this purposes, since the code is written for humans and we should make our code understandable and semantic.

THOMAS H. CORMEN
CHARLES E. LEISERSON
RONALD L. RIVEST
CLIFFORD STEIN
Introduction to algorithms
2008
Massachusetts Institute of technology