Day 18: Algorithms Explained in a Beginner-Friendly Way

Screenshot:-

I am practicing DSA in C++ previously. So, please you can solve more questions for practice or refer Videos to learn algorithms, then easily you will write code in javascript.

Today, we'll dive into some fundamental algorithms used in computer science. We'll explore sorting, searching, string manipulation, and array operations. Additionally, we'll touch on dynamic programming. Let's break down each activity with simple examples and code.

Activity 1: Sorting Algorithms

Task 1: Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Example Code:

function bubbleSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n-1; i++) {
    for (let j = i+1; j < n; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90])); // Output: [11, 12, 22, 25, 34, 64, 90]

Explanation:

• Compares each pair of adjacent elements and swaps them if they are in the wrong order.

• Repeats the process until the array is sorted.

Task 2: Selection Sort

Selection Sort divides the list into two parts: the sorted part at the beginning and the unsorted part at the end. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.

Example Code:

function selectionSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    let temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }
  return arr;
}

console.log(selectionSort([64, 25, 12, 22, 11])); // Output: [11, 12, 22, 25, 64]

Explanation:

• Finds the smallest element in the unsorted part and swaps it with the first unsorted element.

• Repeats the process for the entire array.

Task 3: Quicksort

Quicksort is a divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the pivot.

Example Code:

function quickSort(arr) {
  if (arr.length <= 1) 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)];
}

console.log(quickSort([10, 7, 8, 9, 1, 5])); // Output: [1, 5, 7, 8, 9, 10]

Explanation:

• Selects a pivot element and partitions the array into elements less than the pivot and elements greater than the pivot.

• Recursively applies the same process to the sub-arrays.

Activity 2: Searching Algorithms

Task 4: Linear Search

Linear Search checks each element in the array until the target value is found or the end of the array is reached.

Example Code:

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

console.log(linearSearch([2, 3, 4, 10, 40], 10)); // Output: 3
console.log(linearSearch([2, 3, 4, 10, 40], 5)); // Output: -1

Explanation:

• Iterates through each element in the array to find the target value.

• Returns the index of the target value if found, otherwise returns -1.

Task 5: Binary Search

Binary Search works on sorted arrays by repeatedly dividing the search interval in half.

Example Code:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    }
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

console.log(binarySearch([2, 3, 4, 10, 40], 10)); // Output: 3
console.log(binarySearch([2, 3, 4, 10, 40], 5)); // Output: -1

Explanation:

• Divides the array into two halves and compares the middle element with the target value.

• If the middle element is the target, returns the index.

• If the target is smaller, searches the left half; otherwise, searches the right half.

Activity 3: String Algorithms

Task 6: Count Character Occurrences

Counts the occurrences of each character in a string.

Example Code:

function countCharacterOccurrences(str) {
  const count = {};
  for (let char of str) {
    count[char] = count[char] ? count[char] + 1 : 1;
  }
  return count;
}

console.log(countCharacterOccurrences("hello world")); 
// Output: { h: 1, e: 1, l: 3, o: 2, ' ': 1, w: 1, r: 1, d: 1 }

Explanation:

• Uses an object to keep track of each character's count.

• Iterates through the string and updates the count for each character.

Task 7: Longest Substring Without Repeating Characters

Finds the longest substring without repeating characters.

Example Code:

function longestSubstringWithoutRepeatingCharacters(str) {
  let maxLength = 0;
  let start = 0;
  const seen = {};
  for (let end = 0; end < str.length; end++) {
    if (seen[str[end]] !== undefined) {
      start = Math.max(start, seen[str[end]] + 1);
    }
    seen[str[end]] = end;
    maxLength = Math.max(maxLength, end - start + 1);
  }
  return maxLength;
}

console.log(longestSubstringWithoutRepeatingCharacters("abcabcbb")); // Output: 3 (abc)

Explanation:

• Uses a sliding window approach to keep track of the current substring without repeating characters.

• Updates the starting index when a repeating character is found.

Activity 4: Array Algorithms

Task 8: Rotate Array by k Positions

Rotates an array by k positions.

Example Code:

function rotateArray(arr, k) {
  k = k % arr.length;
  return arr.slice(-k).concat(arr.slice(0, -k));
}

console.log(rotateArray([1, 2, 3, 4, 5], 2)); // Output: [4, 5, 1, 2, 3]

Explanation:

• Uses array slicing to rotate the array.

• Handles cases where k is larger than the array length by using the modulo operator.

Task 9: Merge Two Sorted Arrays

Merges two sorted arrays into one sorted array.

Example Code:

function mergeSortedArrays(arr1, arr2) {
  let merged = [];
  let i = 0, j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      merged.push(arr1[i]);
      i++;
    } else {
      merged.push(arr2[j]);
      j++;
    }
  }
  return merged.concat(arr1.slice(i)).concat(arr2.slice(j));
}

console.log(mergeSortedArrays([1, 3, 5], [2, 4, 6])); // Output: [1, 2, 3, 4, 5, 6]

Explanation:

• Uses two pointers to iterate through both arrays and merge them in sorted order.

Activity 5: Dynamic Programming (Optional)

Task 10: Fibonacci Sequence

Solves the Fibonacci sequence using dynamic programming.

Example Code:

function fibonacciDP(n) {
  const fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib[n];
}

console.log(fibonacciDP(10)); // Output: 55

Explanation:

• Uses an array to store Fibonacci numbers and builds the solution from the base cases.

Task 11: Knapsack Problem

Solves the knapsack problem using dynamic programming.

Example Code:

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][capacity];
}

console.log(knapsack([1, 2, 3], [10, 20, 30], 5)); // Output: 50

Explanation:

• Uses a 2D array to store the maximum value that can be obtained for each sub-problem.