iankiku
10/22/2018 - 9:41 AM

## Algorithms in JavaScript

Algorithms to know. Recursion Binary Search

``````// What is Merge Sort?
// Merge sort is one of the commonly used sorting algorithms in computer science. It is used by Firefox and Safari in their implementation of Array.prototype.sort() (remember how JavaScript behaves differently in different browsers?). It has good performance, it’s easy to implement and understand.
// https://hackernoon.com/programming-with-js-merge-sort-deb677b777c0

// Split the array into halves and merge them recursively
function mergeSort (arr) {
if (arr.length === 1) {
// return once we hit an array with a single item
return arr
}

const middle = Math.floor(arr.length / 2) // get the middle item of the array rounded down
const left = arr.slice(0, middle) // items on the left side
const right = arr.slice(middle) // items on the right side

return merge(
mergeSort(left),
mergeSort(right)
)
}

// compare the arrays item by item and return the concatenated result
function merge (left, right) {
let result = []
let indexLeft = 0
let indexRight = 0

while (indexLeft < left.length && indexRight < right.length) {
if (left[indexLeft] < right[indexRight]) {
result.push(left[indexLeft])
indexLeft++
} else {
result.push(right[indexRight])
indexRight++
}
}

return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight))
}

const list = [2, 5, 1, 3, 7, 2, 3, 8, 6, 3]
console.log(mergeSort(list)) // [ 1, 2, 2, 3, 3, 3, 5, 6, 7, 8 ]``````
``````// What is Insertion Sort?
// Insertion sort is another popular sorting algorithm, even though it’s not as performant as quick sort or merge sort, for example. The way it works is that it splits the array into two sections — a sorted and an unsorted one. We don’t know if any of the items are in place yet, so we will start our sorted list with the first item (an array of a single item is sorted).

// https://hackernoon.com/programming-with-js-insertion-sort-1316df8354f5

function insertionSort (items) {
for (var i = 0; i < items.length; i++) {
let value = items[i]
// store the current item value so it can be placed right
for (var j = i - 1; j > -1 && items[j] > value; j--) {
// loop through the items in the sorted array (the items from the current to the beginning)
// copy each item to the next one
items[j + 1] = items[j]
}
// the last item we've reached should now hold the value of the currently sorted item
items[j + 1] = value
}

return list
}

const list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
console.log(insertionSort(list)) // [ 17, 20, 26, 31, 44, 54, 55, 77, 93 ]``````
``````// Binary search is an algorithm used to find a particular item in a sorted list. It’s essential for the list to be sorted beforehand or the algorithm won’t be applicable. If you’ve ever dealt with binary search trees, this concept of this algorithm is similar.

function binarySearch (list, value) {
// initial values for start, middle and end
let start = 0
let stop = list.length - 1
let middle = Math.floor((start + stop) / 2)

// While the middle is not what we're looking for and the list does not have a single item
while (list[middle] !== value && start < stop) {
if (value < list[middle]) {
stop = middle - 1
} else {
start = middle + 1
}

// recalculate middle on every iteration
middle = Math.floor((start + stop) / 2)
}

// if the current middle item is what we're looking for return it's index, else return -1
return (list[middle] !== value) ? -1 : middle
}

const list = [2, 5, 8, 9, 13, 45, 67, 99]
console.log(binarySearch(list, 99)) // 7 -> returns the index of the item``````
``````  // https://hackernoon.com/programming-with-js-recursion-31371e2bf808
``````