Principais Algoritmos em TypeScript: Implementações e Aplicações

Neste artigo, vamos explorar alguns dos algoritmos mais importantes e comuns que você pode implementar utilizando TypeScript. Esses algoritmos são amplamente utilizados para resolver problemas em áreas como ordenação, busca, grafos e programação dinâmica. Ao implementá-los, você entenderá melhor como funcionam e como podem ser aplicados em diferentes contextos. Vamos explorar cada um desses algoritmos:

1. Algoritmos de Ordenação

Bubble Sort

O Bubble Sort é um algoritmo simples de ordenação que funciona repetidamente trocando elementos adjacentes que estão na ordem errada. Embora seja fácil de entender, não é muito eficiente para grandes conjuntos de dados.

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]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // Troca de elementos
            }
        }
    }
    return arr;
}

Merge Sort

O Merge Sort é um algoritmo eficiente de ordenação que segue o princípio de divisão e conquista. Ele divide o array em partes menores, ordena-as e, em seguida, combina-as para formar o array final.

function mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
    let result = [];
    while (left.length && right.length) {
        result.push(left[0] < right[0] ? left.shift()! : right.shift()!);
    }
    return result.concat(left, right);
}

Quick Sort

O Quick Sort também é baseado em divisão e conquista, mas escolhe um elemento como pivô e particiona o array em sub-arrays que são, então, ordenados recursivamente.

function quickSort(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
    const pivot = arr[arr.length - 1];
    const left = arr.filter(el => el < pivot);
    const right = arr.filter(el => el > pivot);
    return [...quickSort(left), pivot, ...quickSort(right)];
}

Insertion Sort

O Insertion Sort percorre os elementos do array e insere cada elemento na posição correta, ordenando o array à medida que avança.

function insertionSort(arr: number[]): number[] {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

2. Algoritmos de Busca

Busca Linear

A Busca Linear é o método mais simples de busca, percorrendo todos os elementos de uma lista até encontrar o valor desejado.

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

Busca Binária

A Busca Binária é um algoritmo mais eficiente que funciona apenas em listas ordenadas, dividindo a lista ao meio a cada iteração até encontrar o elemento desejado.

function binarySearch(arr: number[], target: number): number {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const 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;
}

3. Algoritmos em Grafos

Dijkstra

O Algoritmo de Dijkstra encontra o caminho mais curto de um vértice a todos os outros em um grafo ponderado, utilizando uma abordagem de exploração de nós e um conjunto de distâncias mínimas.

Busca em Largura (BFS)

A Busca em Largura (BFS) percorre todos os vértices de um grafo camada por camada, sendo útil para encontrar o caminho mais curto em grafos não ponderados.

Busca em Profundidade (DFS)

A Busca em Profundidade (DFS) explora o máximo possível ao longo de cada ramificação antes de retroceder, sendo útil para exploração de grafos e detecção de ciclos.

4. Programação Dinâmica

Fibonacci

A sequência de Fibonacci pode ser calculada eficientemente usando programação dinâmica, armazenando os resultados intermediários para evitar recálculos.

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

Problema da Mochila (Knapsack Problem)

O Problema da Mochila é um clássico problema de otimização que pode ser resolvido utilizando programação dinâmica para encontrar o valor máximo que pode ser obtido, dado um conjunto de itens com pesos e valores.

5. Outros Algoritmos Comuns

Algoritmo de Kadane

O Algoritmo de Kadane é usado para encontrar a submatriz com a soma máxima dentro de uma matriz, resolvendo o problema de soma máxima de subarray em tempo linear.

Algoritmo de Prim

O Algoritmo de Prim encontra a árvore geradora mínima em um grafo, conectando todos os vértices com o menor peso possível.

Algoritmo de Kruskal

Semelhante ao algoritmo de Prim, o Algoritmo de Kruskal também encontra a árvore geradora mínima, mas usa uma abordagem baseada em conjuntos e ordenação das arestas.

Conclusão

Esses algoritmos são fundamentais para resolver uma variedade de problemas em ciência da computação. Implementá-los em TypeScript é uma excelente maneira de aprimorar suas habilidades de programação, ao mesmo tempo em que compreende como funcionam internamente. Seja para ordenação, busca, grafos ou otimização, esses algoritmos desempenham um papel crucial na resolução de problemas complexos de forma eficiente.

Para facilitar os usos dos algoritimos criei uma biblioteca

algoritims - npm

[](https://www.npmjs.com/package/algoritims) [](h. Latest version: 1.0.5, last published: 2 months ago. Start using algoritims in your project by running `npm i algoritims`. There are no other projects in the npm registry using algoritims.

npmjs.com