Given a data set almost any programmer can write a function that gives you what you want from it. Normally we just use the find method, which looks through each item and returns the first one that matches the specified criteria. But once it gets to companies, the concern shifts from simply getting something from a data set to getting something efficiently. That is where algorithms come into play.
An algorithm is a way to solve a problem. For any problem any algorithm can be used, but they will vary in efficiency based on the nature of the data set that one is working with. For example, while it is normally not efficient to search through a set item by item, if for every data set the item you wanted to return was always the first item in the set, doing so would be more efficient then the more complicated algorithms such as binary sort (will explain what this is later) even though binary sort should generally be more efficient. Without further ado, some basic algorithms:
Binary Search
- The binary search is a method that only works on a sorted array. It is a method to quickly find a specific value. The middle value of the array is compared to the desired value, if its lower you take the portion of the array to the left of that middle value, and repeat the process, while if its higher you take the portion to the right and repeat the process. Something like:
let desiredValue = 3let array = [1, 2, 3, 4, 5, 6, 7, 8, 9]let currentValue = nullwhile (currentValue !== desiredValue) {
if(array.length > 1) {
currentValue = array[Math.floor(array.length/2)]
if (currentValue > desiredValue) {
array = array.slice(0, Math.floor(array.length/2))
} else {
array.slice(Math.floor(array.length/2) + 1, array.length)
}
} else {
currentValue = array[0]
}
}return currentValue
In the above example, if the desired value is 3, it will compare the currentValue of null to 3, then since the two are not equal, it will set the current value to the array’s middle value (4). It will then compare the desiredValue (3) vs the currentValue (4), and since the desiredValue is smaller, it will set the array to the numbers to the left the currentValue ([1, 2, 3]). It will repeat the process, the currentValue will be 2, and since 2 < 3, this time the array will be set to the numbers to the right ([3]). Now since the array only has one element left, currentValue is set equal to it, now we break out of the while loop and return the currentValue of 3, which is equal to the desired value.
Bubble Sort
This is probably the most basic way of sorting something, and what someone might do if just told to make a formula that properly sorts an array of numbers. In bubble sort, you iterate an array and compare a value with the value ahead of it, and if the value ahead is bigger swap the two positions, otherwise continue to the next number. After going through the whole thing, you repeat the process from the start again with the exception of the last number, since that is now guaranteed to be the biggest one and in the right place.
It might look something like:
let array = [5, 1, 3, 4, 2]
let swapped = truewhile(swapped === true) {
swapped = false for (let i = 0; i < array.length - 1, i++){
if (array[i] > array[i+1]) {
let var2 = array[i+1]
array[i+1] = array[i]
array[i] = var2
swapped = true
}
i++
}
}return array
Since swapped starts as true, the loop runs. Each time the current value is compared with the value in front, and if the current is bigger the two swap places. Swapped is then set to true, so the loop will run again in case more changes are needed. I is incremented so this process is done for every number. When the loop starts again, swapped is set to false, that way if no swaps are done in this coming iteration, we will break out of the loop and return the correctly ordered array. This is however, one of the worst possible ways of sorting something since it basically brute forces each item individually and changes them, making it one of the slowest sorting algorithms with a complexity of O(n²) where n is the number of items being sorted.This is because the process is basically repeatedly done with the same number of items used.
Quick Sort
Quick sort is one of the most common and fastest sorts. For quick sort first an element is picked (the pivot). Sort the array such that every element smaller then the pivot is to the left, and all elements larger are to the right. These steps are repeated until the mini arrays only contain one or zero elements. The mini one element array are the combined again to create a sorted array.
let array = [5, 1, 3, 4, 2]function quickSort(array) {
if (array.length <= 1) {
return array;
} else {var smaller = []
var bigger = []
var sortedArray = []
var pivot = array.pop()for (var i = 0; i < array.length; i++) {
if (array[i] <= pivot) {
smaller.push(array[i])
} else {
bigger.push(array[i])
}
}return sortedArray.concat(quickSort(smaller), pivot, quickSort(bigger));
}
}
The array’s length is > 1, so in this case we will choose the final value, 2, for our pivot. It will then go through and push values smaller then or equal to 2 into the smaller array ([1])and values larger then 2 into the bigger array ([5, 3, 4]). On the return, it will recursively call itself again when doing quickSort(smaller) and quickSort(bigger). quickSort(smaller) will return the array of 1, since it has a length of 1. So so far it is returning sortedArray.concat([1], 2, quickSort(bigger)). quickSort(bigger) will then take the bigger array [5, 3, 4] and run the process again: pivot = 4, smaller = 3, bigger = 5. This will return sortedArray.concat([3], 4, [5]). Since sortedArray = [], it will end up returning [3, 4, 5]. This will then be used in our original return: sortedArray.concat([1], 2, [3, 4, 5]). sortedArray is [], so we get back [1, 2, 3, 4, 5].
These are a couple of the more commonly seen algorithms or various degrees of usefulness. There are a lot out of different algorithms out there, but no single one is best for all situations; remember to use the best one for your specific needs!