Algorithms — why, when, where

Recursion

When we have data in the hierarchal/nested format, iteration through recursion becomes first choice to do that. In recursion, method (function) call themselves until a certain condition is met. But have to be very careful as if it doesn’t end (condition never met), it cause Stackoverflow. As I explained in my previous article on Data structure, Stack DS is best for function calls, when we put something indefinitely in any data structure, that’s overflow.

class Inception
{
function KeepDreaming(){
//Do something

KeepDreaming();
}
}
function fibonacciIterative(n){
let arr = [0, 1];
for (let i = 2; i < n + 1; i++){
arr.push(arr[i - 2] + arr[i -1]);
}
return arr[n];
}
fibonacciIterative(3);
function fibonacciRecursive(n) {
if (n < 2){
return n;
}
return fibonacciRecursive(n - 1) + fibonacciRecursive (n - 2)
}
fibonacciRecursive(6)

Sorting

Sorting is very important especially when dealing with big data, most of the time when we working/developing commercial business applications, its no big deal but when we need to work on medium to the large size of application with large data to process, sorting could be quite a time/space complexity wise.

Bubble Sort

Probably one the easiest to implement and worst-performing in most cases as no pain no gain. The reason I want to start with this is its simple to implement. so just to revise it, you compare each element with the next one and swap elements if needed and you keep doing it until you don’t see it needed any more, but as it is done through nested loops so you can imagine its time complexity is O(n ^ 2) but space complexity is not bad. Just to jog your memory look at the code below

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
function bubbleSort(array) {
const length = array.length;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length; j++) {
if(array[j] > array[j+1]) {
//Swap the numbers
let temp = array[j]
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
bubbleSort(numbers);
console.log(numbers);

Selection Sort

It’s not much different from Bubble sort int terms of performance but implementation wise. It doesn’t swap with next element instead it swaps with the smallest item in the series.

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
function selectionSort(array) {
const length = array.length;
for(let i = 0; i < length; i++){
// set current index as minimum
let min = i;
let temp = array[i];
for(let j = i+1; j < length; j++){
if (array[j] < array[min]){
//update minimum if current is lower that what we had previously
min = j;
}
}
array[i] = array[min];
array[min] = temp;
}
return array;
}
selectionSort(numbers);
console.log(numbers);

Insertion Sort

It’s better than the above two in many ways and quite natural in terms of implementation. As when you go through the items, you compare with next one if it is smaller you swap but not only with itself, you keep comparing and swapping with all previous items and insert it into its right place once for all.

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
function insertionSort(array) {
const length = array.length;
for (let i = 0; i < length; i++) {
if (array[i] < array[0]) {
//move number to the first position
array.unshift(array.splice(i,1)[0]);
} else {
// only sort number smaller than number on the left of it. This is the part of insertion sort that makes it fast if the array is almost sorted.
if (array[i] < array[i-1]) {
//find where number should go
for (var j = 1; j < i; j++) {
if (array[i] >= array[j-1] && array[i] < array[j]) {
//move number to the right spot
array.splice(j,0,array.splice(i,1)[0]);
}
}
}
}
}
}
insertionSort(numbers);
console.log(numbers);

Merge Sort

Finally, some sorting algorithm which doesn’t rely on nested loops and has better time complexity than O(n²), in fact, its worst, best and avg times are same O(n log(n))

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
function mergeSort (array) {
if (array.length === 1) {
return array
}
// Split Array in into right and left
const length = array.length;
const middle = Math.floor(length / 2)
const left = array.slice(0, middle)
const right = array.slice(middle)

return merge(
mergeSort(left),
mergeSort(right)
)
}
function merge(left, right){
const result = [];
let leftIndex = 0;
let rightIndex = 0;
while(leftIndex < left.length &&
rightIndex < right.length){
if(left[leftIndex] < right[rightIndex]){
result.push(left[leftIndex]);
leftIndex++;
} else{
result.push(right[rightIndex]);
rightIndex++
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const answer = mergeSort(numbers);
console.log(answer);

Quick sort

Quicksort also works in Divide & conquer rule and very efficient. Performance-wise in avg and best scenario, it’s same as Merge sort but in worst case scenario it’s quite worst than Merge sort so chooses wisely, know your data before you choose your algorithm.

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
function quickSort(array, left, right){
const len = array.length;
let pivot;
let partitionIndex;
if(left < right) {
pivot = right;
partitionIndex = partition(array, pivot, left, right);

//sort left and right
quickSort(array, left, partitionIndex - 1);
quickSort(array, partitionIndex + 1, right);
}
return array;
}

function partition(array, pivot, left, right){
let pivotValue = array[pivot];
let partitionIndex = left;
for(let i = left; i < right; i++) {
if(array[i] < pivotValue){
swap(array, i, partitionIndex);
partitionIndex++;
}
}
swap(array, right, partitionIndex);
return partitionIndex;
}
function swap(array, firstIndex, secondIndex){
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
//Select first and last index as 2nd and 3rd parameters
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers);

Heap sort

Heap sort applies on Binary Heap data structure only and very efficient, especially in term of space complexity as it sorts in place so no extra space is needing.

Counting sort visualization

Radix sort visualization

Search Algorithms

There are different search algorithms e.g, linear, binary, BFS, DFS. For revision purposed I’ll talk about some of these and others:

Linear search

Definitely most simplest and that’s why most popular but kind of not very efficient kind of search it is as in worst case you have to go through all items at least ones. Nevertheless, you can use this search on any kind of data, its universally applicable and can be applied to any type of data whereas other search. Time complexity wise O(n)

Binary search

When you hear binary, quickly understand, its something to do with either this or that, with binary search, if there is a list of items, you don’t start your search from start or bottom of the list, you start from the middle if it doesn’t match, you see if the number is bigger or smaller if smaller you move to left otherwise left and then again compare the middle item of that side of the list. so, in that case, you rule out very quickly one side of the list which saves time but it can’t be applied on non sorted data if data is sorted then only you can apply otherwise you never going to get right results. Time complexity wise its O(n log(n))

Traversel Techniques — BFS vs DFS

When we learn tree/graph data structure, we are explained in simple numbers but in real world applications we have more complex data than just simple numbers, we have objects containing different kind of information like names, age, address and when we store them in tree/graph format and have to search through them, we can’t just compare each node with binary search it becomes more of a linear search then as we have to go through all nodes so then we need to decide what would be best technique, how we added our data in tree structure. With BFS, we search all elements on each level and with DFS we search child nodes on one side then move to other, its better explained in illustration below:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
M Adnan A

M Adnan A

3 Followers

Love writing, learning, sharing and love being sarcastic :)