Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and 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]));Selection Sort divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list.
function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
// Find the minimum element in the unsorted array
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
let temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
console.log(selectionSort([64, 25, 12, 22, 11]));Insertion Sort works by building a sorted array (or list) one item at a time, with the input elements being picked one at a time and placed in their correct position.
function insertionSort(arr) {
let n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
return arr;
}
console.log(insertionSort([12, 11, 13, 5, 6]));Merge Sort is a divide and conquer algorithm that divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [], leftIndex = 0, 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));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));Quick Sort is also a divide and conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot.
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).concat(pivot, quickSort(right));
}
console.log(quickSort([10, 7, 8, 9, 1, 5]));Linear Search is the simplest searching algorithm. It checks each element of the list sequentially until a match is found or the whole list has been searched.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1; // Target not found
}
console.log(linearSearch([2, 3, 4, 10, 40], 10)); // Output: 3
console.log(linearSearch([2, 3, 4, 10, 40], 5)); // Output: -1Binary Search is a much faster search algorithm but requires the list to be sorted. It works by repeatedly dividing the search interval in half.
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;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Target not found
}
console.log(binarySearch([2, 3, 4, 10, 40], 10)); // Output: 3
console.log(binarySearch([2, 3, 4, 10, 40], 5)); // Output: -1Jump Search is an algorithm for sorted arrays that checks fewer elements than Linear Search by jumping ahead by fixed steps or blocks and then performing a linear search within the block.
function jumpSearch(arr, target) {
let n = arr.length;
let step = Math.floor(Math.sqrt(n));
let prev = 0;
while (arr[Math.min(step, n) - 1] < target) {
prev = step;
step += Math.floor(Math.sqrt(n));
if (prev >= n) {
return -1;
}
}
while (arr[prev] < target) {
prev++;
if (prev === Math.min(step, n)) {
return -1;
}
}
if (arr[prev] === target) {
return prev;
}
return -1;
}
console.log(jumpSearch([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610], 55)); // Output: 10
console.log(jumpSearch([0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610], 50)); // Output: -1Interpolation Search is an improved variant of Binary Search best suited for uniformly distributed data. It estimates the position of the target value within the sorted array.
function interpolationSearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low === high) {
if (arr[low] === target) {
return low;
}
return -1;
}
let pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] === target) {
return pos;
}
if (arr[pos] < target) {
low = pos + 1;
} else {
high = pos - 1;
}
}
return -1;
}
console.log(interpolationSearch([10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47], 18)); // Output: 4
console.log(interpolationSearch([10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47], 25)); // Output: -1Exponential Search works by finding the range where the target value is present and then performing a Binary Search within that range. It is especially useful for unbounded or infinite lists.
function binarySearch(arr, left, right, target) {
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;
}
function exponentialSearch(arr, target) {
if (arr[0] === target) {
return 0;
}
let i = 1;
while (i < arr.length && arr[i] <= target) {
i = i * 2;
}
return binarySearch(arr, i / 2, Math.min(i, arr.length - 1), target);
}
console.log(exponentialSearch([2, 3, 4, 10, 40], 10)); // Output: 3
console.log(exponentialSearch([2, 3, 4, 10, 40], 5)); // Output: -1BFS explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
if (this.adjacencyList[vertex1]) {
this.adjacencyList[vertex1].push(vertex2);
}
if (this.adjacencyList[vertex2]) {
this.adjacencyList[vertex2].push(vertex1);
}
}
bfs(start) {
const queue = [start];
const result = [];
const visited = {};
visited[start] = true;
while (queue.length) {
const currentVertex = queue.shift();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return result;
}
}
// Example usage:
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');
console.log(graph.bfs('A')); // Output: [ 'A', 'B', 'C', 'D', 'E', 'F' ]DFS explores as far as possible along each branch before backtracking.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
if (this.adjacencyList[vertex1]) {
this.adjacencyList[vertex1].push(vertex2);
}
if (this.adjacencyList[vertex2]) {
this.adjacencyList[vertex2].push(vertex1);
}
}
dfsIterative(start) {
const stack = [start];
const result = [];
const visited = {};
visited[start] = true;
while (stack.length) {
const currentVertex = stack.pop();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return result;
}
}
// Example usage:
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');
console.log(graph.dfsIterative('A')); // Output: [ 'A', 'C', 'E', 'F', 'D', 'B' ]class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
if (this.adjacencyList[vertex1]) {
this.adjacencyList[vertex1].push(vertex2);
}
if (this.adjacencyList[vertex2]) {
this.adjacencyList[vertex2].push(vertex1);
}
}
dfsRecursive(start) {
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
(function dfs(vertex) {
if (!vertex) return;
visited[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach(neighbor => {
if (!visited[neighbor]) {
return dfs(neighbor);
}
});
})(start);
return result;
}
}
// Example usage:
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');
console.log(graph.dfsRecursive('A')); // Output: [ 'A', 'B', 'D', 'E', 'C', 'F' ]