Data Structures and Algorithms with JavaScript

Bubble Sort:

Bubble sorting is the simplest sorting algorithm. It simply iterates over the entire array and swaps elements if one is bigger than the other

//EXAMPLE:1
function swap(array, index1, index2) {
  let temp = array[index1];
  array[index1] = array[index2];
  array[index2] = temp;
}

function bubbleSort(array) {
  // get array length
  let arrLength = array.length;

  // iterate over array
  for (let i=0; i<arrLength; i++) {
    for (let j=0; j<=i; j++) {
      if (array[i] < array[j]) {        
        swap(array, i, j);
      }
    }
  }
  return array;
}

let myArr = [6,3,1,2,4,5];

console.log("Before Sort: ", myArr);

let result = bubbleSort(myArr); 

console.log("After Sort: ", result);
// [1,2,3,4,5,6]

// ----------------------------------------
// EXAMPLE:2 ONE MORE IMPLEMENTATION USING DO WHILE LOOP

function bubbleSort(arr){
  let arrLen = (arr.length - 1);
  let swapped;
  do{
    swapped = false;
    for(let i=0; i<arrLen; i++){
  
      if(arr[i] > arr[i+1]){
        let temp = arr[i];
        arr[i]=arr[i+1];
        arr[i+1]=temp;
        swapped = true;
      }     
    }
  } while(swapped)
}

const arr = [8,20,-2,4,-6,1];
bubbleSort(arr);
console.log(arr);

Selection Sort:

Selection sorting works by scanning the elements for the smallest element and inserting it into the current position of the array. This algorithm is marginally better than bubble sort.

function swap(a,b,arr){	
  let temp = arr[a];
  arr[a]=arr[b];  
  arr[b]=temp;
}

function selectionSort(arr){
  let arrLen = arr.length;
  for(let i=0; i<=arrLen; i++){
    let min = i;
    for(let j=i+1; j<arr.length; j++){
      if(arr[j] < arr[min]){      
        min = j
      }   
    }
    
    if(i != min){
       swap(i, min, arr);         
    }    
  }
  console.log("result =>", arr);
}

//let myArr = [3,2,1,4,5,11,50,22,7];
let myArr = [7,5,1,8];
selectionSort(myArr);

Insertion Sort:

Insertion sort works similarly to selection sort by searching the array sequentially and moving the unsorted items into a sorted sublist on the left side of the array.

function insertionSort(items) {
    // the value currently being compared      
    let value;
    // i index into unsorted section, j index into sorted section      
    let i; 
    let j;
  
    for (i = 0; i < items.length; i++) {
      // store the current value because it may shift later
      value = items[i];

      // Whenever the value in the sorted section is greater than the value
      // in the unsorted section, shift all items in the sorted section over
      // by one. This creates space in which to insert the value.      
      console.log("i:",i);
      for (j = i - 1; j > -1 && items[j] > value; j--) {
        console.log("j:",j);
        items[j + 1] = items[j];
      }
      items[j + 1] = value;
      console.log("items:",items);
    }
    return items;
}
let result = insertionSort([7,4,3,1,5,6,2]);
console.log("Sorted Array: ", result);

Merge Sort

Merge sort algorithm uses the divide and conquer approach to sort the elements. It divides the given list into two equal halves, calls itself for the two halves and then merges the two sorted halves. We have to define the merge() function to perform the merging. The sub-lists are divided again and again into halves until the list cannot be divided further. Then we combine the pair of one element lists into two-element lists, sorting them in the process. The sorted two-element pairs is merged into the four-element lists, and so on until we get the sorted list.

function mergesort(arr) {
  if (arr.length < 2) {
    return arr
  }
  const mid = Math.floor(arr.length / 2)
  const leftArr = arr.slice(0, mid)
  const rightArr = arr.slice(mid)
  return merge(mergesort(leftArr), mergesort(rightArr))
}

function merge(leftArr, rightArr) {
  const sortedArr = []
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] <= rightArr[0]) {
      sortedArr.push(leftArr.shift())
    } else {
      sortedArr.push(rightArr.shift())
    }
  }
  const resultArr = [...sortedArr, ...leftArr, ...rightArr]
  return resultArr
}

const arr = [8, 20, -2, 4, -6]
console.log(mergesort(arr)) // [-6, -2, 4, 8, 20]

Quick Sort

QuickSort picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

You can pick random element as pivot

You can pick last element as pivot

You can pick first element as pivot

You can pick median element as pivot

function quickSort(arr) {
  if (arr.length < 2) return arr
  let pivot = arr[arr.length - 1]
  let left = []
  let right = []
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)]
}

const arr = [8, 20, -2, 4, -6]
console.log(quickSort(arr)) // [-6, -2, 4, 8, 20]

Cartesian Product

It is product of two sets A and B, denoted by AxB, is set of all ordered pairs(a,b) where a is in A and b is in B.

Example: A=[1,2] and B=[3,4] then AxB = [[1,3],[1,4],[2,3],[2,4]].

/*
Cartesian Product: It is product of two sets A and B, denoted by AxB, is set of all ordered pairs(a,b) where a is in A and b is in B.

Example: A=[1,2] and B=[3,4] then AxB = [[1,3],[1,4],[2,3],[2,4]].

*/


function cartesianProduct(arr1,arr2){
  const result = [];
  arr1.forEach((value,index)=>{
    
    arr2.forEach((value2,index2)=>{
      result.push([value,value2])
    });
    
  });
  return result;
}

const arr1=[1,2,3];
const arr2=[4,5,6,7];

let result = cartesianProduct(arr1,arr2);
console.log(result);
// [[1, 4], [1, 5], [1, 6], [1, 7], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7]]