Basic Algorithms in JavaScript
Factorial
Factorial is a way of calculating the multiplication values from a specific value to 1. e.g, 5!= 5*4*3*2*1=120.
The time complexity of factorial is O(n!)
Factorial can be done using two ways. Iterative and recursive.
Iterative
All we need here is just a variable to result and a loop to calculate.
function fact(num){
if(num==0){
return 1
}
else{
return num*fact(num-1)
}
}
console.log(fact(5))
Recursive
We need a condition if the number is 0, then it will be stopped.
function fact(num){
var res= 1;
for(var n = num; n>0; n — ){
res= res*n;
}
console.log(res)
}
fact(0)
Fibbonacci
Fibbonacci is mathematical series named after Leonardo Fibbonacci. The first two numbers in this series is 0 and 1. All other numbers are summation of the last two digits. e.g the third digit is 1 because 0+1=1.
The time complexity of factorial is O(n).
Iterative
It will return only 0 when you pass 1 to the function. Otherwise it will show more than 1 value.
function fibbo(num){
var a=0
var b=1
if(num<=1){
console.log(a)
}
else{
console.log(a)
console.log(b)
for(var n=3; n<=num; n++){
var c=a+b
a=b;
b=c
console.log(c)
}
}
}
fibbo(10)
Recursive
It follow the array indexing which means the 0th value will be the first value.
function fibbo(n){
if(n===1){
return [0,1];
}
var s = fibbo(n — 1);
s.push(s[s.length — 1] + s[s.length — 2]);
return s;
}
console.log(fibbo(10))
Linear Search
Searching all elements to find an element in an array is known as linear search. It’s time complexity is O(n).
Iterative
function linear_search(arr, n){
for(var i=0; i<arr.length; i++){
if(arr[i]===n){
return `${n} is available at index ${i}`;
}
}
return `${n} is not available in the array`;
}
console.log(linear_search([1,2,3,4,5],3))
Recursive
function linear_search(arr,n, key){
if(n>arr.length){
return `${n} is not available in the array`
}
if(arr[n]===key){
return `${key} is available at index ${n}`
}
return linear_search(arr,n+1,key)
}
console.log(linear_search([1,2,3,4,5],0,3))
Binary Search
Searching an element from a sorted array. It is a divide and conquer algorithm. It’s time complexity is O(logn).
Iterative
function binary_search(arr,f,l,key){
while(f<=l){
var mid= f+(l-1)/2
if(arr[mid]===key){
return `${key} is available at index ${mid}`
}
else if(arr[mid]<key){
f=mid+1
}
else{
l=mid-1
}
}
return `${key} is not available in the array`
}
var a=[1,5,8,2,3,4]
a=a.sort()
console.log(binary_search(a,0,a.length-1, 2))
Recursive
function binary_search(a,f,l,key){
if(f<=l){
mid= f+(l-1)/2
if(a[mid]===key){
return `${key} is available at index ${mid}`
}
else if(a[mid]>key){
return binary_search(a, f, mid-1, key)
}
else{
return binary_search(a, mid+1, l,key)
}
}
else{
return `${key} is not available in the array`
}
}
var a=[1,5,8,2,3,4]
a=a.sort()
console.log(binary_search(a,0,a.length-1, 2))
Bubble Sort
Bubble sort is a basic sorting algorithm. It repeatedly swaps elements if they are wrong in order.
It’s time complexity is O(n2).
function bubble(arr){
for(var i=0; i<arr.length-1;i++){
for(var j=i+1; j<arr.length;j++){
if(arr[i]>arr[j]){
[arr[i],arr[j]]=[arr[j],arr[i]]
}
}
}
return arr
}
console.log(bubble([7,5,2,9,1]))
Insertion Sort
Insertion sort is another simple sorting algorithm. It sorts element from a specific starting index to a specific ending index. It’s time complexity is O(n2).
function insertion(arr){
for(var i=1; i<arr.length; i++){
for(var j=0; j<i; j++){
if(arr[i]<arr[j]){
[arr[i], arr[j]]=[arr[j], arr[i]]
}
}
}
return arr;
}
console.log(insertion([7,5,2,9,1]))
Selection Sort
Selection sort is another sorting algorithm. It finds the elements lowest to highest and sort them. It’s time complexity is O(n2).
function selection(arr){
for(var i=0; i<arr.length-1; i++){
var min_idx= i;
for(var j=i+1; j<arr.length; j++){
if(arr[min_idx]>arr[j]){
min_idx=j
}
}
if(arr[i]>arr[min_idx]){
[arr[i], arr[min_idx]]=[arr[min_idx], arr[i]]
}
}
return arr;
}
console.log(selection([7,5,2,9,1]))