Different View of Fundamental JavaScript Algorithms.

Describe both iterative and recursive way.

Credit: Socket.io

Imagine it’s a beautiful morning, you are getting up from the bed and sitting on the sofa, clicking on the button of the TV in a relaxed mode to watch TV. Then, you realize you need to make your breakfast Afterall you are a bachelor by the way. There is a sequence of steps you need to follow to make your breakfast. This sequence of steps is called an algorithm. Clear!!!

Now take a long breath and try to introduce your breakfast ingredients.

Linear search:

It’s a searching algorithm that is used to find whether a number is present in an array or not. If it’s present, then at what location it occurs. It is also known as a sequential search. It is straightforward and works as follows: we compare each element with the target element to search until we find it or the list ends.

Linear search algorithm works in O(N) time complexity

Recursive Method:

function linearSearch(arr,key) {
  function linearSearchRec(list, idx) {
     if (!list.length) return -1;
        const [head, …tail] = list;
     if (key === head) return idx;
      else return linearSearchRec(tail, idx + 1);
      }
   return linearSearchRec(arr, 0);
}
console.log(linearSearch([1,2,3,4,5,6], 5));

Iterative Method:

function linearSearch(arr,key)
{
for (let i = 0; i < arr.length; i++)
if (arr[i] == x)
return i;
return “Not Found”;
}
console.log(linearSearch([5,11,7,8,9],21))
//output: Not Found

Binary Search:

Binary Search is a searching technique that works depends on the Divide and Conquer approach. It used to search any element in a sorted array.

Time Complexity: O(logN)

Recursive Method:

const binaryFunction =(arr, x, start, end) => {
if (start > end) return “Not Found”;
let mid=Math.floor((start + end)/2);
if (arr[mid]===x) return mid;
if(arr[mid] > x) return binaryFunction(arr, x, start, mid-1);
else return binaryFunction(arr, x, mid+1, end);
}
let arr = [1, 3, 5, 7, 8, 9];
let x = 5;
console.log(binaryFunction(arr, x, 0, arr.length-1));
//output: 2

Iterative Method:

const iterativeFunction =(arr, key) => {
let start=0, end=arr.length-1;
while (start<=end){
let mid=Math.floor((start + end)/2);
if (arr[mid]===key) return mid;
else if (arr[mid] < key)
start = mid + 1;
else
end = mid — 1;
}
return “Not Found”;
}
// Driver code
const arr = [1, 3, 5, 7, 8, 9];
const key = 5;
console.log(iterativeFunction(arr, key));

Fibonacci numbers:

Fibonacci numbers are the numbers such that every number in the series after the first two is the sum of the two preceding ones. The series starts with 0, 1. Example −

0,1, 1, 2, 3, 5, 8, 13, 21

Recursive Function:

const fib = number {
const result = [0, 1];
for (var i = 2; i < n; i++) {
result.push(result[i-2] + result[i-1]);
}
return result;
}
console.log(fib(8));

Iterative method:

const fib= (n)=>{
const fibArr = [0,1];
let prevs = 0;
let curr = 1;
let next;
if(n===1) return fibArr;
for(let i = 1;i<n;i++){
next = prevs + curr;
fibArr.push(next);
prevs = curr;
curr = next;
}
return fibArr;
}
console.log(fib(8));
//output:[1,1,2,3,5,8,13,21]

Factorial:

The factorial of a natural number is a number multiplied by “number minus one”, then by “number minus two”, and so on till 1. The factorial of n is denoted as n!

We can write a definition of factorial like this:

n! = n * (n — 1) * (n — 2) * …*1

Recursive:

function rFact(num)
{
if (num === 0)
{ return 1; }
else
{ return num * rFact( num — 1 ); }
}
console.log(rFact(4));

Iterative:

function iFact(num)
{
var rval=1;
for (var i = 2; i <= num; i++)
rval = rval * i;
return rval;
}
console.log(iFact(4));

Bubble Sort:

Bubble Sort is a simple Sorting algorithm that works like as —

• Iterate through the array and check each element against the next element in the array.
• If the current element is larger than the next element, swap them.
• If it’s not greater, move the pointers up and compare the next two elements.
• Once we reach the end of the array, we know that the largest element is in the last position.
• Repeat this process N times where N is the length of the array, and each time, iterate up to the last-sorted element.

Implementation:

function bubbleSort(arr) {
for (let j = arr.length — 1; j > 0; j — ) {
for (let i = 0; i < j; i++) {
if (arr[i] > arr[i + 1]) {
let temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
return arr;
}
console.log(bubbleSort([5,8,7,9,3,1]))

Insertion sort:

Insertion sort will use the current item as a “key”, and then search through the items to the left of that item in the input list for the place that the key should go. This means that the sub-list to the left of the current “key” will already be sorted, and will remain sorted after every iteration of insertion sort

Implementation:

let insertionSort = (inputArr) => {
for (let i = 1;length = inputArr.length,i < length; i++) {
let key = inputArr[i];
let j = i — 1;
while (j >= 0 && inputArr[j] > key) {
inputArr[j + 1] = inputArr[j];
j = j — 1;
}
inputArr[j + 1] = key;
}
return inputArr;
};
console.log(insertionSort([10,5,9,25,47,125]))

Selection Sort:

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n-1 elements of A. This type of sorting is known as selection sort.

Implementation:

function selectionSort(items){
let min;
for (i=0;len = items.length, i < len; i++){
min = i;
for (j=i+1; j < len; j++){
if (items[j] < items[min]){
min = j;
}
}
if (i != min){
swap(items, i, min);
}
}
return items;
}
console.log(selectionSort([10,5,9,25,47,125]));

Huh…Yeah!!! Finally, we have done for today. Bye for now. Happy Learning.