Hi, I'm Tuan, a Full-stack Web Developer from Tokyo 😊. Follow my blog to not miss out on useful and interesting articles in the future.
As a developer, you're probably familiar with the concept of algorithms. But if data structures and algorithms aren't your thing, don't worry. In this article, we'll go over the six key algorithms that every developer should know. These six algorithms can almost always solve any problem you'll encounter in your development process.
1. Sorting Algorithm
Sorting is the process of arranging items in a list in a specific order. The most common types of sorting algorithms include:
Bubble Sort
Bubble sort is the most basic sorting algorithm. It works by repeatedly swapping adjacent elements if they are out of order.
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
console.log(bubbleSort([5, 3, 8, 2, 1, 4])); // [1, 2, 3, 4, 5, 8]
Merge Sort
Merge sort uses the "divide and conquer" strategy. It divides an array into two halves, sorts each half, and then merges the sorted halves back together.
function mergeSort(arr) {
if (arr.length < 2) return arr;
let middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
return result;
}
console.log(mergeSort([5, 3, 8, 2, 1, 4])); // [1, 2, 3, 4, 5, 8]
Quick Sort
Quicksort is a popular sorting algorithm that performs n log n comparisons on average when sorting an array of n elements. It is a more efficient and faster sorting algorithm.
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).concat(pivot, quickSort(right));
}
console.log(quickSort([5, 3, 8,2, 1, 4])); // [1, 2, 3, 4, 5, 8]
Heap Sort
Heap sort works by visualizing the array elements as a special type of complete binary tree known as a heap. The process of heapifying an array is repeated until the array is sorted.
function heapSort(arr) {
let n = arr.length;
for (let i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (let i = n - 1; i >= 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, n, i) {
let largest = i;
let l = 2 * i + 1;
let r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, n, largest);
}
}
console.log(heapSort([5, 3, 8, 2, 1, 4])); // [1, 2, 3, 4, 5, 8]
2. Searching Algorithm
Searching is the process of finding an element in a data set. Common types of searching algorithms include:
Binary Search
Binary search uses the "divide and conquer" strategy. It divides a sorted list into two halves and compares the target value to the middle element. If a match is found, the middle element's location is returned.
function binarySearch(arr, x) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let middle = Math.floor((left + right) / 2);
if (arr[middle] === x) {
return middle;
} else if (arr[middle] < x) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5, 8], 4)); // 3
Breadth-First Search (BFS)
Breadth-first search is a graph traversal algorithm that begins at the root node and explores all neighboring nodes.
function breadthFirstSearch(root, target) {
let queue = [root];
while (queue.length) {
let node = queue.shift();
if (node.value === target) return node;
queue.push(...node.children);
}
return null;
}
Depth-First Search (DFS)
Depth-first search is a graph traversal algorithm that begins at the first node of the graph and goes deeper and deeper until the goal node or node with no children is found.
function depthFirstSearch(node, target) {
if (node.value === target) return node;
for (let child of node.children) {
let found = depthFirstSearch(child, target);
if (found) return found;
}
return null;
}
3. Dynamic Programming
Dynamic programming (DP) is an algorithmic technique that solves an optimization problem by breaking it down into simpler sub-problems and taking advantage of the fact that the optimal solution to the overall problem is dependent on the optimal solution to its sub-problems. A common example is the problem of computing the nth Fibonacci number.
function fibonacci(n) {
let dp = [];
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(fibonacci(5)); // 5
In this example, we use an array dp to store the intermediate results of each sub-problem (the Fibonacci numbers up to the nth). This allows us to avoid redundant computation, greatly reducing the time complexity of the algorithm.
4. Recursion Algorithm
Recursion is a problem-solving technique in which the solution is dependent on solutions to smaller instances of the same problem. A classic example of recursion is computing factorials.
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120
5. Divide and Conquer
Divide and conquer is a general algorithmic strategy that involves breaking a problem down into smaller sub-problems and solving each sub-problem independently. An example of divide-and-conquer algorithm is the problem of finding the closest pair of points in a set of points in a 2-dimensional space.
function closestPair(points) {
let minDistance = Number.MAX_SAFE_INTEGER;
let closestPair = [];
points.sort((a, b) => a.x - b.x);
for (let i = 0; i < points.length - 1; i++) {
for (let j = i + 1; j < points.length; j++) {
let distance = Math.sqrt(
(points[i].x - points[j].x) ** 2 + (points[i].y - points[j].y) ** 2
);
if (distance < minDistance) {
minDistance = distance;
closestPair = [points[i], points[j]];
}
}
}
return closestPair;
}
console.log(
closestPair([
{ x: 0, y: 0 },
{ x: 3, y: 4 },
{ x: 1, y: 1 },
{ x: 2, y: 2 },
{ x: 5, y: 6 },
])
);
In this example, the algorithm first sorts the points by their x-coordinates. Then, for each point, it compares its distance to all the points that come after it in the sorted array, updating the minimum distance and closest pair if a closer pair is found.
Hashmap
A Hashmap is a data structure that stores key-value pairs and allows for constant-time O(1) insertion, deletion, and lookup. It works by taking the key and applying a hash function to it, which returns an index in an array, the element of that index is called a bucket. The value is then stored in that bucket.
class HashMap {
constructor() {
this.buckets = Array(10)
.fill(null)
.map(() => []);
this.keys = this.keys = {};
}
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.buckets.length;
}
set(key, value) {
let index = this.hash(key);
for (let bucket of this.buckets[index]) {
if (bucket[0] === key) {
bucket[1] = value;
return;
}
}
this.buckets[index].push([key, value]);
this.keys[key] = value;
}
get(key) {
let index = this.hash(key);
for (let bucket of this.buckets[index]) {
if (bucket[0] === key) {
return bucket[1];
}
}
return null;
}
delete(key) {
let index = this.hash(key);
let i = 0;
for (let bucket of this.buckets[index]) {
if (bucket[0] === key) {
this.buckets[index].splice(i, 1);
delete this.keys[key];
return;
}
i++;
}
}
}
let map = new HashMap();
map.set("name", "John Smith");
map.set("age", 30);
console.log(map.get("name")); // "John Smith"
console.log(map.get("age")); // 30
map.delete("name");
console.log(map.get("name")); // null
In this example, we created a HashMap class which has properties buckets, keys and methods hash, set, get, delete. The hash method takes a key as an input, converts it into a numerical value, and returns the index of the corresponding bucket in the array. The set, get, and delete methods use the hash method to find the appropriate bucket, then add, retrieve, or remove the key-value pair as appropriate.
Hashmap is a powerful data structure that is used in a wide range of scenarios, such as caching, implementing dictionaries, or storing large amounts of data. Knowing how to use Hashmap will be helpful in a wide range of problems you will encounter as a developer.
Conclusion
Understanding and mastering six key algorithms is crucial for any developer.
The six algorithms are:
- Sorting algorithms: bubble sort, merge sort, quick sort, heap sort
- Searching algorithms: binary search, breadth-first search, depth-first search
- Dynamic programming
- Recursion
- Divide and conquer
These algorithms are fundamental building blocks of computer science and are used in a wide range of problems, from sorting and searching data, to optimizing complex problems. Understanding and practicing these algorithms will improve your development skills and make you a more efficient and effective programmer. Additionally, learning these algorithms will give you a solid foundation of computer science knowledge that will be useful regardless of the programming language you are working with.
Understanding and using Hashmap is an important skill for a developer as well, it's a data structure that can help you to efficiently store, retrieve, and modify large amounts of data.
Each of these algorithms comes with its own use cases, strengths and weaknesses. Mastering all of them will help you choose the right algorithm to solve any specific problem you may encounter in your development career.
As always, I hope you enjoyed this article and learned something new. Thank you and see you in the next articles!
If you liked this article, please give me a like and subscribe to support me. Thank you. 😊