Description: Bubble Sort is a simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Time Complexity:
- Worst-case: O(n²)
- Best-case: O(n) (when already sorted)
Space Complexity: O(1)
Use Cases: Efficient for small datasets, used for ordering data like search results and table entries.
function bubbleSort(arr: number[]): number[] {
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]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
return arr;
}Description: QuickSort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
Time Complexity:
- Average and Best-case: O(n log n)
- Worst-case: O(n²)
Space Complexity: O(log n)
Use Cases: Generally efficient for larger datasets, used in complex sorting needs like multi-key sorting.
function quickSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1];
const leftArr = [];
const rightArr = [];
for (const el of arr.slice(0, -1)) {
el < pivot ? leftArr.push(el) : rightArr.push(el);
}
return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
}Description: Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.
Time Complexity: O(log n)
Space Complexity: O(1)
Use Cases: Efficient for lookups in sorted data, used in features like auto-complete where fast retrieval is necessary.
function binarySearch(arr: number[], target: number): number {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) start = mid + 1;
else end = mid - 1;
}
return -1;
}Graph algorithms are essential for solving complex problems related to network structures, such as social networks, computer networks, and road maps. Here’s an overview of some fundamental graph algorithms with added details on data structures and an example of ASCII art representing a graph.
Before diving into algorithms, it's crucial to understand how graphs can be represented in code. The two most common representations are adjacency lists and adjacency matrices.
Adjacency List: This is the most common way to represent graphs. Each node (or vertex) stores a list of adjacent nodes. In TypeScript, this can be a Map or an array of lists.
Example:
type Graph = Map<number, number[]>;
let graph: Graph = new Map([
[1, [2, 3]], // Node 1 is connected to Node 2 and 3
[2, [1, 4]], // Node 2 is connected to Node 1 and 4
[3, [1]], // Node 3 is connected to Node 1
[4, [2]] // Node 4 is connected to Node 2
]);ASCII Art Representation:
1 -- 2
| |
3 4
This graph shows the connections between four nodes. Nodes 1 and 2 are connected, as are 1 and 3, and 2 and 4.
Description: DFS is an algorithm for traversing or searching tree or graph data structures. It starts at the root and explores as far as possible along each branch before backtracking.
Time Complexity: O(V + E) where V is vertices and E is edges.
Space Complexity: O(V)
Use Cases: Useful for complex data structures like trees or graphs, used in scenarios like network routing and social networking analysis.
type Graph = Map<number, number[]>;
function dfs(graph: Graph, node: number, visited = new Set<number>()) {
visited.add(node);
const neighbors = graph.get(node);
if (neighbors) {
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
return visited;
}Description: BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
Time Complexity: O(V + E)
Space Complexity: O(V)
Use Cases: Good for finding the shortest path and exploring all neighbors at one depth, used in scenarios like AI decision-making and pathfinding in games.
function bfs(graph: Graph, startNode: number) {
const visited = new Set<number>();
const queue: number[] = [startNode];
while (queue.length > 0) {
const node = queue.shift();
if (node && !visited.has(node)) {
visited.add(node);
const neighbors = graph.get(node);
if (neighbors) {
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
}
}
}
}
}
return visited;
}Description: Dijkstra's Algorithm is a famous algorithm for finding the shortest path between nodes in a graph, which may represent, for example, road networks.
Time Complexity: O(V²) but can be reduced to O(V + E log V) with the help of priority queues.
Space Complexity: O(V)
Use Cases: GPS navigation systems, network routing protocols, and in AI for finding the shortest path.
Example Data Structure: Typically implemented using a priority queue and adjacency list for efficient retrieval and updates.
function dijkstra(graph: Graph, startNode: number): Map<number, number> {
const distances = new Map<number, number>();
graph.forEach((_, node) => distances.set(node, Infinity));
distances.set(startNode, 0);
const priorityQueue = new PriorityQueue<number>();
priorityQueue.add(startNode, 0);
while (!priorityQueue.isEmpty()) {
const currentNode = priorityQueue.poll();
const currentDist = distances.get(currentNode);
for (const neighbor of graph.get(currentNode) || []) {
const dist = currentDist + 1; // assuming edge weight of 1
if (dist < (distances.get(neighbor) || Infinity)) {
distances.set(neighbor, dist);
priorityQueue.add(neighbor, dist);
}
}
}
return distances;
}When choosing an algorithm, consider not only the size of the data but also the nature of the operation and the typical use case in your application. For instance, algorithms with higher worst-case time complexity might still be the best practical choice for certain scenarios with small datasets or where the worst case is rare.