O que são os algoritmos de Dividir para Conquistar?

Dividir para conquistar é um paradigma algorítmico semelhante ao paradigma Greedy (ou "ambicioso") e ao paradigma da Programação Dinâmica. Um algoritmo de dividir para conquistar típico resolve um problema usando os passos a seguir.

1. Dividir: quebrar o problema em subproblemas do mesmo tipo. Esse passo envolve a divisão de um problema em subproblemas menores. Os subproblemas devem representar uma parte do problema original. Esse passo geralmente assume uma abordagem recursiva para dividir o problema até que nenhum subproblema possa ser dividido ainda mais. Nesse estágio, subproblemas se tornam atômicos por natureza, mas ainda representam alguma parte do problema em questão.
2. Conquistar: resolver recursivamente esses subproblemas. Esse passo recebe vários subproblemas menores para serem resolvidos. Em geral, nesse nível, os problemas são considerados "resolvidos" por eles mesmos.
3. Combinar: combinar adequadamente as respostas. Quando os subproblemas menores são resolvidos, esse estágio os combina recursivamente até que eles formulem uma solução para o problema original. Essa abordagem algorítmica funciona recursivamente e os passos de conquistar e unir ficam tão próximos que parecem ser apenas um.

Esse método geralmente permite que haja uma grande redução na complexidade de tempo.

Por exemplo, a Bubble Sort (ordenação de "bolha") usa uma complexidade de O(n^2), enquanto o quicksort (ordenação rápida, uma aplicação do tipo Dividir para Conquistar) reduz a complexidade de tempo para O(nlog(n)). A busca linear tem complexidade de tempo de O(n), enquanto a busca binária (uma aplicação do tipo Dividir para Conquistar) reduz a complexidade de tempo para O(log(n)).

A seguir, vemos alguns algoritmos padrão que são do tipo Dividir para Conquistar.

A busca binária  (em inglês, Binary Search)é um algoritmo de pesquisa. Em cada etapa, o algoritmo compara o elemento de entrada (x) com o valor do elemento do meio em um array. Se o valor corresponder, retorna-se o índice do meio. Do contrário, se x for menor que o elemento do meio, o algoritmo faz a recursão para percorrer o lado à esquerda do elemento do meio. Se for maior, faz a recursão para percorrer o lado à direita do elemento do meio.

A ordenação rápida (em inglês, Quick Sort) é um algoritmo de ordenação. O algoritmo seleciona um elemento pivô, reorganiza os elementos do array de tal maneira que todos os elementos menores que o elemento de pivô selecionado sejam movidos para a esquerda do pivô, enquanto todos os elementos maiores que o elemento de pivô selecionado sejam movidos para a direita dele. Por fim, o algoritmo recursivamente ordena os subarrays à esquerda e à direita do elemento de pivô.

A ordenação por mistura (em inglês, Merge Sort) também é um algoritmo de ordenação. O algoritmo divide o array em duas metades, as ordena recursivamente e, finamente, mistura as duas metades ordenadas. A complexidade de tempo desse algoritmo é de O(nLogn) no melhor caso, no caso médio ou no pior caso. Sua complexidade de tempo pode ser entendida facilmente do fato de que a recorrência/recursão tem como equação: T(n) = 2T(n/2) + n.

O par de pontos mais próximos: o problema é encontrar o par de pontos mais próximo em um conjunto de pontos em um plano x-y (ou cartesiano). O problema pode ser resolvido com uma complexidade de tempo de O(n^2) calculando as distâncias de cada par de pontos e comparando as distâncias para encontrar a distância menor. O algoritmo de Dividir para Conquistar resolve o problema em tempo de O(nLogn).

O algoritmo de Strassen é um algoritmo eficaz para a multiplicação de duas matrizes. Um método simples para multiplicar duas matrizes precisa de 3 laços aninhados e tem como complexidade de tempo O(n^3). O algoritmo de Strassen multiplica duas matrizes com complexidade de tempo de O(n^2.8974).

O algoritmo de transformada rápida de Fourier (FFT), de Cooley–Tukey é o algoritmo mais comum para a FFT. Ele é um algoritmo de dividir para conquistar que funciona com complexidade de tempo de O(nlogn).

O algoritmo de Karatsuba foi o primeiro algoritmo de multiplicação assintoticamente mais rápido que o algoritmo quadrático padrão. Ele reduz a multiplicação de dois números de n algarismos a, no máximo, n^1,585  (que é uma aproximação do log de 3 na base 2) produtos de um único algarismo. Ele é, portanto, mais rápido do que o algoritmo clássico, que exige n^2 produtos de um único algarismo.

Dividir para conquistar x Programação dinâmica

Os dois paradigmas dividem o problema em questão em subproblemas e resolvem os subproblemas. Como selecionar um dos paradigmas para determinado problema? Dividir para conquistar deve ser usado quando os mesmos subproblemas não são avaliados várias vezes. Do contrário, deve-se usar a programação dinâmica ou a memoização.

Por exemplo, a busca binária é um algoritmo de dividir para conquistar. Nele, jamais avaliamos os mesmos subproblemas novamente. Por outro lado, para calcular o n-ésimo número de Fibonacci, deve-se preferir a programação dinâmica.

O algoritmo de preenchimento por inundação (do inglês, flood fill) é usado principalmente para determinar uma área limitada conectada a um determinado nó em uma matriz multidimensional. É muito semelhante à ferramenta do balde em programas como o Microsoft Paint.

A implementação mais usada do algoritmo é uma função recursiva baseada em pilha (em inglês, stack), e é sobre isso que falaremos a seguir.

Como funciona?

O problema é bastante simples e sua solução, geralmente, segue os passos abaixo:

1. Assuma a posição como ponto de partida.
2. Decida se quer ir nas quatro direções (N, S, O, L) ou em 8 direções (N, S, O, L, NO, NE, SO, SE).
3. Escolha uma cor substituta e uma cor de destino.
4. Viaje nas direções selecionadas.
5. Se o bloco no qual você parar for da cor de destino, substitua a cor pela cor substituta.
6. Repita os passos 4 e 5 até ter chegado a todos os lugares dentro dos limites.

Vamos pegar a matriz multidimensional abaixo como exemplo:

O quadrado vermelho é o ponto de partida e os quadrados em cinza são os limites.

Para mais detalhes, veja um trecho do código que descreve a função:

int wall = -1;

void flood_fill(int pos_x, int pos_y, int target_color, int color)
{
  
   if(a[pos_x][pos_y] == wall || a[pos_x][pos_y] == color) // se não houver um limite ou se eu já não estive lá
      return;                                              // volte
   
   if(a[pos_x][pos_y] != target_color) // se não for da cor, volte
      return;
   
   a[pos_x][pos_y] = color; // marque o ponto de modo que eu saiba que passei por ele. 
   
   flood_fill(pos_x + 1, pos_y, color);  //depois, posso ir para o sul
   flood_fill(pos_x - 1, pos_y, color);  // o norte
   flood_fill(pos_x, pos_y + 1, color);  // o leste
   flood_fill(pos_x, pos_y - 1, color);  // ou o oeste
   
   return;

}

Como vemos acima, meu ponto de partida é (4,4). Depois de chamar a função para as coordenadas de início, x = 4 e y = 4, posso começar a conferir se há ou não um limite ou uma cor no local. Se for válido, marco o local com uma cor (color) e começo a verificar os quadrados adjacentes.

Indo para o sul, chegarei ao ponto (5,4) e a função é executada novamente.

Problema do exercício

Sempre considerei que resolver um ou mais problemas usando um algoritmo recém aprendido é a melhor maneira de entender o conceito por completo.

Aqui temos um problema:

Instrução: em uma matriz bidimensional, você recebe um número n fornecido de "ilhas". Tente achar a maior área de uma ilha e o número da ilha correspondente. 0 significa água e qualquer outro x entre 1 e n significa um quadrado da superfície correspondente à ilha x.

Entradas

• n – o número de ilhas.
• l, c – as dimensões da matriz.
• o próximo número, onde l é a linha e c é a coluna, dando a l-ésima linha da matriz.

Resultado

• i – o número da ilha com a maior área.
• A - a área da i-ésima ilha.

Exemplo:

Você tem a entrada abaixo:

2 4 4
0 0 0 1
0 0 1 1
0 0 0 2
2 2 2 2

Para qual delas você terá a ilha número 2 como sendo a maior área, com 5 quadrados.

Dicas

O problema é bem fácil, mas aqui você tem algumas dicas:

1. Use o algoritmo de preenchimento por inundação sempre que encontrar uma nova ilha.
2. Diferente do que ocorre no código de exemplo, você deve percorrer a ára da ilha, não a do oceano (blocos com 0).

Para tratarmos deste assunto, primeiramente, é preciso conhecer a respeito do máximo divisor comum (MDC ou GCD – no inglês, Greatest Common Divisor) e da operação MOD (de módulo).

Máximo divisor comum (MDC ou GCD)

O MDC de dois ou mais números inteiros é o maior número inteiro que divide es números anteriormente mencionados de tal modo que o resto da divisão é zero.

Exemplo:
O MDC de 20 e 30 é 10  (10 é o maior número que divide 20 e 30 com o resto 0)
O MDC de 42, 120, 285 = 3  (3 é o maior número que divide 42, 120 e 285 com o resto 0)

Operação "mod"

O operador de módulo (mod) mostra o resto da divisão quando dividimos dois números inteiros. Escrevemos isso assim:
A mod B = R

Isso significa que, ao dividir A e B, temos o resto R. Essa operação difere da operação regular de divisão, que nos dá o quociente.

Exemplo:
7 mod 2 = 1  (Ao dividir 7 por 2 temos o resto 1)
42 mod 7 = 0  (Ao dividir 42 por 7 temos o resto 0)

Tendo entendido os dois conceitos acima, será fácil de entender o algoritmo de Euclides.

Algoritmo de Euclides para o máximo divisor comum (MDC ou GCD)

O algoritmo de Euclides encontra o máximo divisor comum (que chamaremos nos algoritmos de 'GCD') de 2 números.

Você entenderá melhor esse algoritmo ao vê-lo em funcionamento. Supondo que você deseja calcular o GCD de 1220 e de 516, vamos aplicar o algoritmo de Euclides:

Pseudocódigo do algoritmo
Passo 1:  suponha que a, b  sejam os dois números
Passo 2:  a mod b = R
Passo 3:  considere que  a = b  e que  b = R
Passo 4:  repita os passos 2 e 3 até que a mod b  seja maior do que 0
Passo 5:  GCD = b
Passo 6: fim

Código em JavaScript para encontrar o GCD:

function gcd(a, b) {
  var R;
  while ((a % b) > 0)  {
    R = a % b;
    a = b;
    b = R;
  }
  return b;
}

Código em JavaScript para encontrar o GCD usando a recursividade:

function gcd(a, b) {
  if (b == 0)
    return a;
  else
    return gcd(b, (a % b));
}

Código em C para encontrar o GCD usando a recursividade:

int gcd(int a, int b) 
{ 
    // Tudo pode ser dividido por 0  
    if (a == 0) 
       return b; 
    if (b == 0) 
       return a; 
  
    // Caso de base 
    if (a == b) 
        return a; 
  
    // a é maior 
    if (a > b) 
        return gcd(a-b, b); 
    return gcd(a, b-a); 
}

Código em C++ para encontrar o GCD:

int gcd(int a,int b) {
  int R;
  while ((a % b) > 0)  {
    R = a % b;
    a = b;
    b = R;
  }
  return b;
}

Código em Python para encontrar o GCD usando recursividade:

def gcd(a, b):
  if b == 0:
    return a:
  else:
    return gcd(b, (a % b))

Código em Java para encontrar o GCD usando recursividade:

static int gcd(int a, int b)
{
  if(b == 0)
  {
    return a;
  }
  return gcd(b, a % b);
}

Você também pode usar o algoritmo de Euclides para encontrar o máximo divisor comum de mais de dois números. Como o GCD é associativo, a operação a seguir também seria válida:  GCD(a,b,c) == GCD(GCD(a,b), c)

Calcule o GCD dos dois primeiros número, depois encontre o GCD do resultado e do número seguinte. Exemplo:  GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Você pode encontra o GCD de  n  números da mesma maneira.

O que é o algoritmo de Euclides estendido?

Esta é uma extensão do algoritmo de Euclides. Ela também calcula os coeficientes x, y, de tal modo que:

ax+by = gcd(a,b)

x e y também são conhecidos como os coeficientes da identidade de Bézout.

Código em C para o algoritmo de Euclides estendido

struct Triplet{
	int gcd;
	int x;
	int y;
};
Triplet gcdExtendedEuclid(int a,int b){
	// Case de base
	if(b==0){
		Triplet myAns;
		myAns.gcd = a;
		myAns.x = 1;
		myAns.y = 0;
		return myAns;

	}
	Triplet smallAns = gcdExtendedEuclid(b,a%b);
	// Algoritmo de Euclides estendido

	Triplet myAns;
	myAns.gcd = smallAns.gcd;
	myAns.x  = smallAns.y;
	myAns.y = (smallAns.x - ((a/b)*(smallAns.y)));
	return myAns;	
}

Tradução realizada em português europeu

Antes de começarmos, vamos discutir o que é o problema da Torre de Hanói. Bem, é um simples puzzle onde o objetivo é mover um bloco completo de discos de uma posição inicial para outra posição. São seguidas três regras simples:

1. Apenas pode ser movido um disco de cada vez.
2. Cada movimento consiste em pegar no disco mais acima na pilha e colocá-lo no topo de outra pilha. Por outras palavras, um disco apenas pode ser movido se for o disco que está mais acima na pilha.
3. Não pode ser colocado um disco maior sobre um menor.

Agora, vamos tentar imaginar um cenário. Vamos supor que temos uma pilha com três discos. O nosso objetivo é mover esta pilha da origem A para o destino C. Como fazemos isto?

Antes de lá chegarmos, vamos imaginar que existe um ponto intermédio B.

Podemos utilizar B como ajuda para completar essa tarefa. Agora, estamos prontos para avançar. Vamos analisar cada um dos passos:

1. Mover o primeiro disco de A para C
2. Mover o primeiro disco de A para B
3. Mover o primeiro disco de C para B
4. Mover o primeiro disco de A para C
5. Mover o primeiro disco de B para A
6. Mover o primeiro disco de B para C
7. Mover o primeiro disco de A para C

Resolvemos o nosso problema!

Podes observar a imagem animada acima para uma compreensão melhor do problema.

Agora, vamos tentar criar o algoritmo para resolver o problema. Espera, temos aqui uma nova palavra: "Algoritmo". O que é isso? Alguma ideia? Sem problema, vamos ver.

O que é um algoritmo?

Um algoritmo é um dos conceitos mais importantes para um programador de software. Na verdade, acho que não é apenas importante para desenvolvimento de software ou programação, mas para toda a gente. Os algoritmos afetam-nos na nossa vida do dia a dia. Vamos ver como.

Vamos supor que trabalhas num escritório. Então, todas as manhãs fazes uma série de tarefas em sequência: primeiro acordas, depois vais à casa de banho, tomas o pequeno-almoço, preparas-te para o trabalho, sais de casa e, depois, podes apanhar um táxi ou autocarro, ou começar a andar em direção ao escritório e, depois de um determinado tempo, chegas ao escritório. Podes dizer que todos esses passos formam um algoritmo.

De forma simples, um algoritmo é um conjunto de tarefas. Espero que não te tenhas esquecido dos passos que realizamos para mover os três discos da pilha A para a C. Também podes dizer que esses passos são o algoritmo para resolver o problema da Torre de Hanói.

Em matemática e ciências da computação, um algoritmo é uma especificação ambígua de como resolver uma classe de problemas. Os Algoritmos podem realizar cálculo, processamento de dados e tarefas de raciocínio automatizado. — Wikipédia

Se observares estes passos, podes ver que fizemos a mesma tarefa várias vezes — mover discos de uma pilha para outra. A esses passos dentro de passos podemos chamar recursividade.

Recursividade

Recursividade é chamar a mesma ação a partir dessa ação, tal como na imagem acima.

Portanto, existe um regra para quando fazemos algum trabalho recursivo: deve existir uma condição para parar a execução da ação. Espero que tenhas compreendido os conceitos básicos sobre recursividade.

Agora, vamos tentar criar um procedimento que nos ajuda a resolver o problema da Torre de Hanói. Estamos a tentar criar a solução utilizando pseudocódigo. Pseudocódigo é um método de escrita de código utilizando a língua inglesa.

tower(disk, source, intermediate, destination)
{

}

Esse é o esqueleto da nossa solução. Recebemos o número total de discos como um argumento. Depois temos de passar a origem, local intermédio e destino de modo a podermos compreender o mapa que vamos utilizar para completar a tarefa.

Agora, precisamos de encontrar um estado terminal. O estado terminal é o estado onde vamos deixar de chamar a função.

IF disk is equal 1

No nosso caso, este seria o nosso estado terminal. Quando existir apenas um disco na pilha, é simples realizar este último passo e, depois disso, a nossa tarefa estará concluída. Não te preocupes se isto não for claro para ti. Quando chegarmos ao final, este conceito será mais claro.

Bem, encontramos o nosso ponto de estado terminal onde movemos o nosso disco para o destino, deste modo:

move disk from source to destination

Agora, chamamos a nossa função novamente ao passar estes argumentos. Neste caso, dividimos a pilha de discos em duas partes. O disco maior (enésimo disco) está numa parte e todos os outros discos (n-1) estão na segunda parte. Aí, chamamos o método duas vezes para (n-1).

tower(disk - 1, source, destination, intermediate)

Tal como indicamos, passamos total_disks_on_stack — 1 como argumento. Então, movemos novamente o nosso disco, deste modo:

move disk from source to destination

Depois disso, chamamos novamente o nosso método, desta forma:

tower(disk - 1, intermediate, source, destination)

Vamos observar o nosso pseudocódigo completo:

tower(disk, source, inter, dest)

IF disk is equal 1, THEN
      move disk from source to destination
   ELSE
      tower(disk - 1, source, destination, intermediate)   // Step 1
      move disk from source to destination                 // Step 2
      tower(disk - 1, intermediate, source, destination)   // Step 3
   END IF
   
END

Esta é a árvore para três discos:

Este é o código completo em Ruby:

def tower(disk_numbers, source, auxilary, destination)
  if disk_numbers == 1
    puts "#{source} -> #{destination}"
    return
  end
  tower(disk_numbers - 1, source, destination, auxilary)
  puts "#{source} -> #{destination}"
  tower(disk_numbers - 1, auxilary, source, destination)
  nil
end

Chama tower(3, 'source','aux','dest')

Resultado:

source -> dest
source -> aux
dest -> aux
source -> dest
aux -> source
aux -> dest
source -> dest

Foram necessários sete passos para os três discos chegarem ao destino. Chamamos a isto um método recursivo.

Cálculo de complexidade de tempo e de espaço

Complexidade de tempo (texto do link em inglês)

Quando executamos código ou uma aplicação na nossa máquina demora tempo — ciclos de CPU. Não é igual em todos os computadores, no entanto. Por exemplo, o tempo de processamento de um Core I7 e de um dual core é diferente. Para resolver este problema, existe um conceito utilizado na ciência da computação chamado complexidade de tempo.

Complexidade de tempo é um conceito em ciências da computação que lida com a quantificação da quantidade de tempo gasto por um conjunto de código ou algoritmo para processar ou executar como uma função da quantidade do input.

Por outras palavras, complexidade de tempo é essencialmente eficiência, ou quanto tempo uma função do programa demora a processar um determinado input. — techopedia

A complexidade de tempo dos algoritmos é geralmente expressada utilizando a notação de O grande. É uma notação assimptótica para representar a complexidade de tempo.

Agora, o tempo necessário para mover n discos é T(n). Existem duas chamadas recursivas para (n-1). Existe uma operação de tempo constante para mover um disco de um ponto inicial para um destino, que seja m1. Portanto:

T(n) = 2T(n-1) + m1    ..... eq(1)

E

T(0) = m2, a constant   ...... eq(2)
From eq (1)
T(1) = 2T(1-1) + m1
     = 2T(0)+m1
     = 2m2 + m1 ..... eq(3) [From eq 2]
T(2) = 2T(2-1) + m1
     = 2T(1) + m1
     = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)]
T(3) = 2T(3-1) + m1
     = 2T(2) + m1
     = 8m2 + 4m1 + 2m1 + m1  [From eq(4)]

A partir destes padrões — eq(2) até ao último — podemos dizer que a complexidade de tempo deste algoritmo é O(2^n) ou O(a^n), onde a é uma constante maior do que 1. Por isso, tem complexidade de tempo exponencial. Para um único aumento no tamanho do problema, o tempo necessário é o dobro do anterior. Isto é computacionalmente muito caro. A maior parte dos programas recursivos recebem tempo exponencial, e é por isso que é muito difícil escrevê-los de maneira iterada.

Complexidade de espaço (texto do link em inglês)

Depois da explicação da análise da complexidade de tempo, acho que consegues adivinhar o que é isso. É o cálculo do espaço necessário em memória RAM para executar código ou uma aplicação.

No nosso caso, o espaço para o parâmetro por cada chamada é independente de n, o que significa que é constante. Que seja J. Quando realizamos a segunda chamada recursiva, a primeira termina. Isso significa que podemos reutilizar o espaço depois de finalizar a primeira. Portanto:

T(n) = T(n-1) + k .... eq(1)
T(0) = k, [constant] .... eq(2)
T(1) = T(1-1) + k
     = T(0) + k
     = 2K
T(2) = 3k
T(3) = 4k

Então, a complexidade de espaço é O(n).

Depois destas análises, podemos ver que a complexidade de tempo deste algoritmo é exponencial, mas a complexidade de espaço é linear.

Conclusão

Depois deste artigo, espero que agora consigas compreender melhor o puzzle da Torre de Hanói e como resolvê-lo. Além disso, tentei fornecer algum conhecimento básico sobre algoritmos, a sua importância, recursividade, pseudocódigo, complexidade de tempo e complexidade de espaço. Se quiseres obter informações mais detalhadas sobre estes tópicos, aqui estão os links para alguns cursos on-line bastante conhecidos:

1. Algoritmos, Parte I, da Coursera
2. Algoritmos, Parte II, da Coursera
3. O Curso da Google da Udacity
4. Certificação em Algoritmos e Estruturas de Dados em JavaScript (300 horas)

Podes visitar o repositório do autor sobre estruturas de dados e algoritmos para ver as outras soluções dele para diversos problemas.

O autor pode ser encontrado nestas redes sociais: GitHub | Twitter | LinkedIn

Oi, pessoal! Neste artigo, vamos dar uma olhada em algoritmos, um tópico chave quando se trata de ciência da computação e desenvolvimento de software.

Algoritmo é uma palavra chique e às vezes intimidadora, mas frequentemente incompreendida. Parece algo muito difícil e complexo, mas, na verdade, nada mais é do que um conjunto de passos que devem ser dados para atingir um determinado objetivo.

Eu diria que o conhecimento básico sobre algoritmos consiste principalmente em duas coisas:

• Notação assintótica (que usamos para comparar o desempenho de um algoritmo com outro).
• Um conhecimento geral de algoritmos clássicos usados ​​para tarefas muito frequentes, como pesquisar, classificar e percorrer.

É exatamente isso que vamos ver aqui.😉
Vamos lá!

Sumário

• O que é um algoritmo?
• Complexidade algorítmica
• Algoritmos de pesquisa
• Pesquisa linear
• Pesquisa binária
• Algoritmos de ordenação
• Ordenação por bolha
• Ordenação por seleção
• Ordenação por inserção
• Ordenação por mistura
• Ordenação rápida
• Ordenação Radix
• Algoritmos de travessia
• Pesquisa por largura (Breadth-first search, ou BFS)
• Pesquisa por profundidade (Depth-first search, ou DFS)
• Pré-ordem por DFS
• Pós-ordem por DFS
• Em ordem por DFS
• Conclusão

O que é um algoritmo?

Como mencionado anteriormente, um algoritmo é apenas um conjunto de etapas que precisam ser executadas em ordem para atingir um determinado objetivo.

Eu acho que quando as pessoas ouvem a palavra algoritmo pela primeira vez, elas imaginam algo assim...

Na verdade, porém, a imagem abaixo seria a mais correta...

Um algoritmo é como uma receita, no sentido de que indicará os passos necessários que precisam ser seguidos para atingir seu objetivo.

Uma receita para fazer pão pode ser:

1- Misture farinha, sal, água e fermento
2- Deixe a massa crescer
3- Leve ao forno por 30 minutos
4- Deixe esfriar e aproveite

Comentário à parte: espero que você aprecie o fato de eu estar ensinando como codificar e cozinhar ao mesmo tempo, tudo de graça. Aproveite que não é sempre! 😜

Um algoritmo para identificar se uma palavra é um palíndromo ou não poderia ser:

function isPalindrome(word) {
    // Passo 1- Colocar um ponteiro em cada extremo da palavra
    // Passo 2 - Percorrer a string "internamente"
    // Passo 3 - A cada iteração, verificar se os ponteiros representam valores iguais
    // Se esta condição não for cumprida, a palavra não é um palíndromo
    let left = 0
    let right = word.length-1

    while (left < right) {
        if (word[left] !== word[right]) return false
        left++
        right--
    }
    
    return true
}

isPalindrome("neuquen") // true
isPalindrome("Buenos Aires") // false

Assim como em uma receita, nesse algoritmo temos etapas com uma determinada finalidade, que são executadas em uma determinada ordem para alcançar o resultado que desejamos.

Seguindo a Wikipédia:

Um algoritmo é uma sequência finita de instruções bem definidas, normalmente usadas para resolver uma classe de problemas específicos ou para realizar uma computação.

Complexidade algorítmica

Agora que sabemos o que é um algoritmo, vamos aprender a comparar diferentes algoritmos entre si.

Digamos que nos é apresentado este problema:

Escreva uma função que receba dois parâmetros: um array não vazio de inteiros distintos e um inteiro representando o resultado desejado. Se quaisquer dois números no array, somados, forem igual ao desejado, a função deve retorná-los em um array. Se não houver dois números que, somados, sejam iguais ao resultado desejado, a função deve retornar um array vazio.

Esta poderia ser uma solução válida para o problema:

function twoNumberSum(array, targetSum) {
    let result = []
    // Usamos um laço aninhado para testar todas as combinações possíveis de números dentro do array
        for (let i = 0; i < array.length; i++) {
          for (let j = i+1; j < array.length; j++) {
              // Se encontrarmos a combinação certa, colocamos ambos os valores no array result e o retornamos
              if (array[i] + array[j] === targetSum) {
                  result.push(array[i])
                  result.push(array[j])
                  return result
              }
          }
      }
      // Retorna o array result
      return result
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

Esta é outra solução válida:

function twoNumberSum(array, targetSum) {
    // Ordenar o array e fazer a iteração por ele com um ponteiro em cada extremo
    // A cada iteração, verificar se a soma dos dois ponteiros é maior ou menor que o alvo
    // Se for maior, mover o ponteiro da direita para a esquerda
    // Se for menor, mover o ponteiro da esquerda para a direita
	let sortedArray = array.sort((a,b) => a-b)
	let leftLimit = 0
	let rightLimit = sortedArray.length-1

	while (leftLimit < rightLimit) {
			const currentSum = sortedArray[leftLimit] + sortedArray[rightLimit]

			if (currentSum === targetSum) return [sortedArray[leftLimit], sortedArray[rightLimit]]
			else currentSum < targetSum ? leftLimit++ : rightLimit--        
	}

	return []
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

E esta é uma terceira solução válida:

function twoNumberSum(array, targetSum) {
    // Iterar sobre o array uma vez e a cada iteração
    // Verificar se o número que você precisa para chegar ao destino existe no array
    // Se existir, retornar seu índice e o índice de número atual
	let result = []

	for (let i = 0; i < array.length; i++) {
        let desiredNumber = targetSum - array[i]
        if (array.indexOf(desiredNumber) !== -1 && array.indexOf(desiredNumber) !== i) {
            result.push(array[i])
            result.push(array[array.indexOf(desiredNumber)])
            break
        }
	}

    return result
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

Então, como podemos comparar qual solução é a melhor? Todas elas cumprem o objetivo, certo?

Mas além da eficácia (se o objetivo é alcançado ou não), devemos também avaliar os algoritmos em termos de eficiência , ou seja, o que resolve o problema usando a menor quantidade de recursos em termos de tempo (tempo de processamento) e espaço (uso de memória).

Um pensamento automático que surge quando se pensa nisso pela primeira vez é: "É só medir quanto tempo leva para o algoritmo ser executado". E isso é válido.

O problema é que o mesmo algoritmo pode demorar mais ou menos tempo em um computador diferente, devido ao seu hardware e configuração. E mesmo no mesmo computador, pode levar mais ou menos tempo para executar, por conta das tarefas em segundo plano que você está executando naquele determinado momento.

O que precisamos é de uma maneira objetiva e invariável de medir o desempenho de um algoritmo, e é justamente para isso que serve a notação assintótica.

A notação assintótica (também chamada de notação Big O) é um sistema que nos permite analisar e comparar o desempenho de um algoritmo à medida que sua entrada aumenta.

Big O é um método padronizado para analisar e comparar a complexidade (em termos de tempo de execução e espaço) de diferentes algoritmos. A complexidade Big O de um algoritmo será sempre a mesma, não importa em qual computador você a "calcule", porque a complexidade é calculada com base no fato de que o número de operações do algoritmo varia quando a entrada varia. Essa relação continua sempre igual, não importando o ambiente de execução.

Existem muitas complexidades possíveis que um algoritmo pode ter, mas as mais comuns são as seguintes:

• Constante — O(1): Quando o número de operações/espaço necessário permanece igual, independentemente da entrada. Tomemos, por exemplo, uma função que recebe um número como entrada e retorna esse número menos 10. Não importa se você inserir 100 ou 1000000 como entrada, essa função sempre executará uma única operação (a subtração de 10), então a complexidade é constante O(1).
• Logarítmica — O(log n): Quando o número de operações/espaço necessário cresce a uma taxa cada vez mais lenta em comparação ao crescimento da entrada. Esse tipo de complexidade é frequentemente encontrada em algoritmos que adotam uma abordagem de dividir e conquistar ou em algoritmos de busca. O exemplo clássico é a busca binária, em que, dado o conjunto de dados, você continuamente passa/corta pela metade até chegar ao resultado final.
• Linear — O(n): Quando o número de operações/espaço necessário cresce na mesma taxa que a entrada. Por exemplo, um laço que imprime todos os valores encontrados em um array. O número de operações crescerá junto com o comprimento do array, então a complexidade é linear O(n).
• Quadrática — O(n²): Quando o número de operações/espaço necessário cresce à potência de dois em relação à entrada. Laços aninhados são o exemplo clássico dessa complexidade. Imagine que temos um laço que itera através de um array de números, e dentro desse laço temos outro que itera todo o array novamente. Para cada valor no array estamos iterando sobre o array duas vezes, então a complexidade é quadrática O(n²).

Observe que a mesma notação é usada quando falamos sobre ambas as complexidades, tempo e espaço. Digamos, por exemplo, que temos uma função que sempre cria um array com um único valor, não importando a entrada que ela receba, então a complexidade do espaço será constante O(1), e assim por diante com os outros tipos de complexidade.

Para entender melhor tudo isso, vamos voltar ao nosso problema e analisar as soluções.

Exemplo 1:

function twoNumberSum(array, targetSum) {
    let result = []
        for (let i = 0; i < array.length; i++) {
          for (let j = i+1; j < array.length; j++) {
              if (array[i] + array[j] === targetSum) {
                  result.push(array[i])
                  result.push(array[j])
                  return result
              }
          }
      }
      return result
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

Neste exemplo, estamos iterando sobre o array de parâmetros e, para cada valor dentro do array, estamos iterando todo o array novamente procurando por um número que, somado, seja igual ao resultado desejado.

Então, cada iteração conta como uma tarefa.

• Se tivéssemos 3 números no array, iteraríamos 3 vezes para cada número e mais 9 vezes (3 vezes os três números do array). Total: 12 tarefas.
• Se tivéssemos 4 números no array, iteraríamos 4 vezes para cada número e mais 16 vezes (4 vezes os quatro números do array). Total: 20 tarefas.
• Se tivéssemos 5 números no array, iteraríamos 5 vezes para cada número e mais 25 vezes (5 vezes os cinco números do array). Total: 25 tarefas.

Você pode ver como o número de tarefas neste algoritmo cresce exponencialmente e desproporcional à entrada. A complexidade para este algoritmo é quadrática – O(n²).

Sempre que vemos laços aninhados, devemos pensar em complexidade quadrática => O QUE É RUIM => Provavelmente, há uma maneira melhor de resolver isso.

Exemplo 2:

function twoNumberSum(array, targetSum) {
	let sortedArray = array.sort((a,b) => a-b)
	let leftLimit = 0
	let rightLimit = sortedArray.length-1

	while (leftLimit < rightLimit) {
			const currentSum = sortedArray[leftLimit] + sortedArray[rightLimit]

			if (currentSum === targetSum) return [sortedArray[leftLimit], sortedArray[rightLimit]]
			else currentSum < targetSum ? leftLimit++ : rightLimit--        
	}

	return []
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

Aqui, estamos classificando o algoritmo antes de iterarmos nele. E só depois, iteramos apenas uma vez, usando um ponteiro em cada extremo do array e iterando "internamente".

Essa solução é melhor do que a anterior, pois estamos iterando apenas uma vez. Ainda estamos, no entanto, classificando o array (que geralmente tem uma complexidade logarítmica) e depois iterando uma vez (que é a complexidade linear). A complexidade algorítmica desta solução é O(n log(n)).

Exemplo 3:

function twoNumberSum(array, targetSum) {
    // Iterar sobre o array uma vez e, a cada iteração
    // verificar se o número que você precisa obter para chegar ao resultado esperado existe no array
    // Se existir, retornar o índice e o índice do número atual
	let result = []

	for (let i = 0; i < array.length; i++) {
        let desiredNumber = targetSum - array[i]
        if (array.indexOf(desiredNumber) !== -1 && array.indexOf(desiredNumber) !== i) {
            result.push(array[i])
            result.push(array[array.indexOf(desiredNumber)])
            break
        }
	}

    return result
}

console.log(twoNumberSum([9,1,3,4,5], 6)) // [1,5]
console.log(twoNumberSum([1,2,3,4,5], 10)) // []

Neste último exemplo, estamos iterando o array apenas uma vez, sem fazer mais nada antes. Essa é a melhor solução, pois estamos realizando o menor número de operações. A complexidade neste caso é linear – O(n) .

Este é realmente o conceito mais importante por trás dos algoritmos. Ser capaz de comparar diferentes implementações e entender qual é mais eficiente e por que é realmente um conhecimento importante de se ter. Portanto, se o conceito ainda não estiver claro para você, eu sugiro ler os exemplos novamente, procurar outros recursos ou conferir esta aula incrível do freeCodeCamp (em inglês).

Algoritmos de pesquisa

Uma vez que você tenha um bom entendimento sobre a complexidade algorítmica, a próxima coisa a saber são os algoritmos populares usados ​​para resolver tarefas de programação muito comuns. Então, vamos começar com as pesquisas.

Ao procurar um valor em uma estrutura de dados, existem diferentes abordagens que podemos adotar. Vamos dar uma olhada em duas das opções mais usadas e compará-las.

Pesquisa linear

A pesquisa linear consiste em iterar sobre a estrutura de dados, um valor por vez, e verificar se esse valor é o que estamos procurando. É, provavelmente, o melhor e mais intuitivo tipo de pesquisa que podemos fazer se a estrutura de dados que estamos usando não estiver ordenada.

Suponha que temos um array de números e que, para esse array, queremos escrever uma função que receba um número como entrada e retorne o índice desse número no array. Caso o número não exista no array, retornamos -1. Uma abordagem possível poderia ser a seguinte:

const arr = [1,2,3,4,5,6,7,8,9,10]

const search = num => {
    for (let i = 0; i < arr.length; i++) {
        if (num === arr[i]) return i
    }
    return -1
}

console.log(search(6)) // 5
console.log(search(11)) // -1

Como o array não está ordenado, não temos como saber a posição aproximada de cada valor, então o melhor que podemos fazer é verificar um valor por vez. A complexidade desse algoritmo é linear - O(n)  e, no pior cenário, teremos que iterar sobre todo o array uma vez para obter o resultado da nossa pesquisa.

A pesquisa linear é a abordagem usada por muitos métodos integrados do JavaScript, como indexOf, includes e findIndex.

Pesquisa binária

Quando temos uma estrutura de dados ordenada, há uma abordagem muito mais eficiente que podemos adotar: a pesquisa binária. O que fazemos na pesquisa (ou busca) binária é o seguinte:

• Selecionamos o valor médio da nossa estrutura de dados e "perguntamos": este é o valor que estamos procurando?
• Se não for, "perguntamos" se o valor que procuramos é maior ou menor que o valor médio
• Se for maior, "descartamos" todos os valores menores que o valor médio. Se for menor, "descartamos" todos os valores maiores que o valor médio.
• Por fim, repetimos a mesma operação até encontrarmos o valor pesquisado ou até não ser mais possível dividir o "pedaço" restante da estrutura de dados.

O que é mais legal na busca binária é que, em cada iteração, estamos descartando aproximadamente metade da estrutura de dados. Isso torna a pesquisa realmente rápida e eficiente. 👌

Suponha que temos o mesmo array (ordenado) e queremos escrever a mesma função de antes, que recebe um número como entrada e retorna o índice desse número no array. Caso ele não exista no array, retornamos -1. Podemos escrever essa pesquisa binária da seguinte forma:

const arr = [1,2,3,4,5,6,7,8,9,10]

const search = num => {
    // Usaremos três ponteiros.
    // Um no início do array, um no final e outro no meio.
    let start = 0
    let end = arr.length-1
    let middle = Math.floor((start+end)/2)

    // Enquanto não encontramos o número, e o ponteiro inicial for igual ou menor ao ponteiro final
    while (arr[middle] !== num && start <= end) {
        // Se o número desejado for menor que o meio, descartamos a metade maior do array
        if (num < arr[middle]) end = middle - 1
        // Se o número desejado for maior que o meio, descartamos a metade menor do array
        else start = middle + 1
        // Recalculamos o valor do meio
        middle = Math.floor((start+end)/2)
    }
    // Se saírmos do laço, significa que encontramos o valor ou que o array não pode mais ser dividido
    return arr[middle] === num ? middle : -1
}

console.log(search(6)) // 5
console.log(search(11)) // -1

Essa abordagem pode parecer "mais código" no início, mas as iterações potenciais são, na verdade, muito menores do que na pesquisa linear. Isso ocorre porque, em cada iteração, estamos descartando aproximadamente metade da estrutura de dados. A complexidade deste algoritmo é logarítmica – O(log n).

Algoritmos de ordenação

Ao ordenar estruturas de dados, existem muitas abordagens que podemos adotar. Vamos olhar algumas das opções mais usadas e compará-las.

Ordenação por bolha

A ordenação por bolha (do inglês Bubble Sort) itera pela estrutura de dados e compara um par de valores por vez. Se a ordem desses valores estiver incorreta, ele troca suas posições para corrigi-la. A iteração é repetida até que os dados estejam ordenados. Esse algoritmo faz com que valores maiores "borbulhem" até o final do array.

Esse algoritmo tem uma complexidade quadrática – O(n²), pois vai comparar cada valor com o resto dos valores uma vez.

Uma forma de fazer isso é:

const arr = [3,2,1,4,6,5,7,9,8,10]

const bubbleSort = arr => {
    // Definir uma variável como flag
    let noSwaps
	
    // Fazer um laço aninhado
    // com um ponteiro iterando da direita para a esquerda
    for (let i = arr.length; i > 0; i--) {
        noSwaps = true
		// e outro iterando da esquerda para a direita
        for (let j = 0; j < i-1; j++) {
            // Comparar os dois ponteiros
            if (arr[j] > arr[j+1]) {
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
                noSwaps = false
            }
        }
        if (noSwaps) break
    }
}

bubbleSort(arr)
console.log(arr) // [1,2,3,4,5,6,7,8,9,10]

Ordenação por seleção

A ordenação por seleção (do inglês Selection Sort) é semelhante à ordenação por bolha, mas, em vez de colocar os valores maiores no final da estrutura de dados, ela se concentra em colocar os valores menores no início. Os passos que executa são:

• Armazenar o primeiro item da estrutura de dados como o valor mínimo.
• Iterar através da estrutura de dados comparando cada valor com o valor mínimo.
• Se um valor menor for encontrado, identificar esse valor como o novo valor mínimo e troca as posições do novo valor mínimo com o antigo.
• Repetir essa iteração até que a estrutura de dados esteja ordenada.

Este algoritmo tem uma complexidade quadrática – O(n²).

Uma forma de fazer isso é assim:

const arr = [3,2,1,4,6,5,7,9,8,10]

const selectionSort = arr => {
    
    for (let i = 0; i < arr.length; i++) {
        let lowest = i
        
        for (let j = i+1; j < arr.length; j++) {
            if (arr[j] < arr[lowest]) {
                lowest = j
            }
        }

        if (i !== lowest) {
            let temp = arr[i]
            arr[i] = arr[lowest]
            arr[lowest] = temp
        }
    }
}

selectionSort(arr)
console.log(arr) // [1,2,3,4,5,6,7,8,9,10]

Ordenação por inserção

A ordenação por inserção (do inglês Insertion Sort) ordena a estrutura de dados criando uma "metade ordenada", que é sempre ordenada corretamente e itera pela estrutura de dados selecionando cada valor e inserindo-o na metade ordenada, no local exato em que deveria estar.

As etapas que ela faz são:

• Começar escolhendo o segundo elemento na estrutura de dados.
• Comparar este elemento com o anterior e trocar suas posições, se necessário.
• Continuar com o próximo elemento e, se não estiver na posição correta, percorrer a "metade ordenada" para encontrar sua posição correta e inserir ali.
• Repetir o mesmo processo até que toda a estrutura de dados esteja ordenada.

A complexidade desse algoritmo é quadrática (O(n²)).

Uma possível aplicação dela é assim:

const arr = [3,2,1,4,6,5,7,9,8,10]

const insertionSort = arr => {
    let currentVal
    
    for (let i = 0; i < arr.length; i++) {
        currentVal = arr[i]

        for (var j = i-1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j+1] = arr[j]
        }
        
        arr[j+1] = currentVal
    }
    
    return arr
}

insertionSort(arr)
console.log(arr) // [1,2,3,4,5,6,7,8,9,10]

O problema com as ordenações por bolha, seleção e inserção é que esses algoritmos não são bem dimensionados (todos de complexidade quadrática).

Há opções muito melhores que podemos escolher quando trabalhamos com grandes conjuntos de dados. Algumas delas são a ordenação por mistura, a rápida e a Radix. Então, vamos dar uma olhada nelas agora!

Ordenação por mistura

A ordenação por mistura (do inglês Merge Sort) é um algoritmo que decompõe recursivamente a estrutura de dados em valores individuais e depois a compõe novamente de forma ordenada.

As etapas dele são:

• Quebrar recursivamente a estrutura de dados em metades até que cada "peça" tenha apenas um valor.
• Em seguida, mesclar recursivamente as partes de forma ordenada até voltar ao tamanho da estrutura de dados original.

Este algoritmo tem complexidade O(n log n), uma vez que a decomposição tem uma complexidade de log n e a comparação tem uma complexidade de n.

Podemos escrevê-lo deste modo:

const arr = [3,2,1,4,6,5,7,9,8,10]

// Função do merge (mistura)
const merge = (arr1, arr2) => {
    const results = []
    let i = 0
    let j = 0

    while (i < arr1.length && j < arr2.length) {
        if (arr2[j] > arr1[i]) {
            results.push(arr1[i])
            i++
        } else {
            results.push(arr2[j])
            j++
        }
    }

    while (i < arr1.length) {
        results.push(arr1[i])
        i++
    }

    while (j < arr2.length) {
        results.push(arr2[j])
        j++
    }

    return results
}

const mergeSort = arr => {
    if (arr.length <= 1) return arr
    let mid = Math.floor(arr.length/2)
    let left = mergeSort(arr.slice(0,mid))
    let right = mergeSort(arr.slice(mid))
    return merge(left, right)
}

console.log(mergeSort(arr)) // [1,2,3,4,5,6,7,8,9,10]

Ordenação rápida

A ordenação rápida (do inglês Quick Sort) funciona selecionando um elemento de "pivô" (ou eixo) e encontrando o índice onde ele deve terminar no array classificado.

O tempo de execução dessa classificação depende em parte de como o pivô é selecionado. Idealmente, deve ser aproximadamente o valor mediano do conjunto de dados que está sendo classificado.

Os passos desse algoritmo são:

• Identificar o valor do pivô e colocá-lo no índice que deveria ser.
• Executar recursivamente o mesmo processo em cada “metade” da estrutura de dados.

Este algoritmo tem uma complexidade O(n log n).

Uma forma de fazer isso é:

const arr = [3,2,1,4,6,5,7,9,8,10]

const pivot = (arr, start = 0, end = arr.length - 1) => {
    const swap = (arr, idx1, idx2) => [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]

    let pivot = arr[start]
    let swapIdx = start

    for (let i = start+1; i <= end; i++) {
        if (pivot > arr[i]) {
            swapIdx++
            swap(arr, swapIdx, i)
        }
    }

    swap(arr, start, swapIdx)
    return swapIdx
}

const quickSort = (arr, left = 0, right = arr.length - 1) => {
    if (left < right) {
        let pivotIndex = pivot(arr, left, right)
        quickSort(arr, left, pivotIndex-1)
        quickSort(arr, pivotIndex+1, right)
    }

    return arr
}

console.log(quickSort(arr)) // [1,2,3,4,5,6,7,8,9,10]

Ordenação Radix

Radix é um algoritmo que funciona de modo diferente dos vistos anteriormente, no sentido de não comparar valores. Ele é usado para ordenar listas de números e, para isso, explora o fato de que o tamanho de um número é definido pelo número de algarismos que ele possui (quanto mais algarismos, maior o número).

O que o Radix faz é ordenar os valores por seus algarismos, em ordem. Ele ordena todos os valores pelo primeiro algarismo, depois novamente pelo segundo, depois pelo terceiro… Este processo é repetido tantas vezes quanto o número de algarismos do maior número da lista. E ao final desse processo, o algoritmo retorna a lista totalmente ordenada.

Os passos que ele faz são:

• Calcular quantos algarismos o maior número tem.
• Percorrer a lista até o maior número de algarismos. Em cada iteração:
• Criar "buckets" para cada algarismo (de 0 a 9) e coloca cada valor em seu bucket correspondente de acordo com o algarismo que está sendo avaliado.
• Substituir a lista existente pelos valores classificados nos buckets, começando em 0 e indo até 9.

Este algoritmo tem uma complexidade O(n*k), sendo k o número de algarismos que o maior número possui. Dado que não compara valores entre si, esse algoritmo tem um tempo de execução melhor do que os vistos anteriormente, mas somente funcionará em listas numéricas.

Se quisermos um algoritmo de ordenação agnóstica de dados, provavelmente usaríamos qualquer um dos anteriores.

Uma possível implementação poderia ser a seguinte:

const arr = [3,2,1,4,6,5,7,9,8,10]

const getDigit = (num, i) => Math.floor(Math.abs(num) / Math.pow(10, i)) % 10

const digitCount = num => {
    if (num === 0) return 1
    return Math.floor(Math.log10(Math.abs(num))) + 1
}

const mostDigits = nums => {
    let maxDigits = 0

    for (let i = 0; i < nums.length; i++) maxDigits = Math.max(maxDigits, digitCount(nums[i]))

    return maxDigits
}

const radixSort = nums => {
    let maxDigitCount = mostDigits(nums)

    for (let k = 0; k < maxDigitCount; k++) {
        let digitBuckets = Array.from({ length: 10 }, () => [])
        
        for (let i = 0; i < nums.length; i++) {
            let digit = getDigit(nums[i], k)
            digitBuckets[digit].push(nums[i])
        }

        nums = [].concat(...digitBuckets)
    }

    return nums
}

console.log(radixSort(arr)) // [1,2,3,4,5,6,7,8,9,10]

Algoritmos de travessia

O último tipo de algoritmo que veremos são os algoritmos de travessia, usados ​​para iterar através de estruturas de dados de formas diferentes (mas, principalmente, árvores e grafos).

Ao iterar uma estrutura de dados como a de árvore, podemos priorizar as iterações de duas formas: profundidade ou largura.

Se priorizarmos a profundidade, vamos "descer" por cada galho da árvore, indo do tronco até a folha de cada galho.

Se priorizarmos a largura, passaremos por cada "nível" da árvore horizontalmente, iterando por todos os nós que estão no mesmo nível antes de "descer" para o próximo nível.

A decisão de qual algoritmo escolher dependerá em grande parte do valor que procuramos em nossa iteração e de como nossa estrutura de dados está construída.

Pesquisa por largura (BFS)

Vamos analisar a BFS primeiro. Como mencionei antes, esse tipo de travessia percorrerá nossa estrutura de dados de modo horizontal. Seguindo esta imagem de exemplo abaixo, os valores seriam percorridos na seguinte ordem: [10, 6, 15, 3, 8, 20].

Normalmente, as etapas seguidas pelos algoritmos BFS são as seguintes:

• Criar uma fila e uma variável para armazenar os nós que foram "visitados"
• Colocar o nó principal dentro da fila
• Continuar fazendo o laço enquanto houver algo na fila
• Retirar um nó da fila e colocar o valor do nó na variável que armazena os nós visitados
• Se houver a propriedade left no nó que foi removido da fila, adicioná-la à fila
• Se houver uma propriedade right no nó que foi removido da fila, adicioná-la à fila

Uma forma de fazer isso é a seguinte:

class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}

class BinarySearchTree {
    constructor(){ this.root = null; }

    insert(value){
        let newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        let current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

    BFS(){
        let node = this.root,
            data = [],
            queue = [];
        queue.push(node);

        while(queue.length){
           node = queue.shift();
           data.push(node.value);
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;
    }
}


const tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.BFS()) // [ 10, 6, 15, 3, 8, 20 ]

Pesquisa por profundidade (DFS)

A DFS por sua vez, fará a iteração através da nossa estrutura de dados de modo vertical. Seguindo o mesmo exemplo que usamos para a BFS, os valores seriam percorridos nessa ordem: [10, 6, 3, 8, 15, 20].

Essa maneira de fazer a DFS é chamada de "pré-ordem". Existem, na verdade, três maneiras principais pelas quais a DFS pode ser feita, a diferença entre elas é apenas a alteração da ordem em que os nós são visitados.

• Pré-ordem: visite o nó atual, depois o nó menor e depois o nó maior.
• Pós-ordem: explore todos os filhos menores e todos os filhos maiores antes de visitar o nó.
• Na ordem: Explore todos os filhos menores, visita o nó atual e explore todos os filhos maiores.

Se isso parece confuso, não se preocupe. Não é tão complexo e ficará mais claro depois com os exemplos.

Pré-ordem por DFS

No algoritmo de pré-ordem por profundidade, seguimos as etapas de:

• Criar uma variável para armazenar os valores dos nós visitados
• Armazenar a raiz da árvore em uma variável
• Escrever uma função auxiliar que aceite um nó como parâmetro
• Adicionar o valor do nó para a variável que armazena os valores
• Se o nó tiver uma propriedade left (que é um filho com valor menor que o atual), chamar a função auxiliar com o nó left como parâmetro
• Se o nó tiver uma propriedade right (que é um filho com valor maior que o atual), chamar a função auxiliar com o nó right como parâmetro

Uma maneira de fazer isso é:

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

    DFSPreOrder(){
        var data = [];
        function traverse(node){
            data.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }

}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSPreOrder()) // [ 10, 6, 3, 8, 15, 20 ]

Pós-ordem por DFS

No algoritmo de pós-ordem por profundidade, fazemos o seguinte:

• Criar uma variável para armazenar os valores dos nós visitados
• Armazenar a raiz da árvore em uma variável
• Escrever uma função auxiliar que aceite um nó como parâmetro
• Se o nó tiver uma propriedade left, chamar a função auxiliar com o nó left como parâmetro
• Se o nó tiver uma propriedade right, chamar a função auxiliar com o nó right como parâmetro
• Adicionar o valor do nó para a variável que armazena os valores
• Chamar a função auxiliar com o nó atual como parâmetro

Uma forma possível de fazer isso é a seguinte:

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }


    DFSPostOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            data.push(node.value);
        }
        traverse(this.root);
        return data;
    }
}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSPostOrder()) // [ 3, 8, 6, 20, 15, 10 ]

Em ordem por DFS

No algoritmo em ordem por profundidade, fazemos o seguinte:

• Criamos uma variável para armazenar os valores dos nós visitados
• Armazenamos a raiz da árvore em uma variável
• Escrevemos uma função auxiliar que aceite um nó como parâmetro
• Se o nó tiver uma propriedade left, chamamos a função auxiliar com o nó left como parâmetro
• Adicionar o valor do nó para a variável que armazena os valores
• Se o nó tiver uma propriedade right, chamamos a função auxiliar com o nó right como parâmetro
• Chamamos a função auxiliar com o nó atual como parâmetro

Uma forma possível de fazer isso é assim:

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

    DFSInOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            data.push(node.value);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
    }
}


var tree = new BinarySearchTree()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

console.log(tree.DFSInOrder()) // [ 3, 6, 8, 10, 15, 20 ]

Como você deve ter notado, as implementações de pré-ordem, pós-ordem e em ordem são quase iguais, pois o que é alterado é apenas a ordem de como os nós são visitados. Porém o resultado de travessia que chegamos em cada um são bem diferentes e, às vezes, uma forma pode ser até mais útil do que as outras.

Em relação a quando usar BFS ou DFS, como eu disse, depende de como nossa estrutura de dados está organizada.

De um modo geral, se tivermos uma árvore ou grafo muito amplo (o que significa que existem muitos nós irmãos no mesmo nível), devemos priorizar a DFS. Se, no entanto, estivermos lidando com uma árvore ou grafo muito grande com ramificações muito longas, devemos priorizar a BFS.

Na questão do tempo, a complexidade dos dois os algoritmos é a mesma, pois estamos sempre visitando cada nó apenas uma vez. A complexidade de espaço, por outro lado, pode ser muito diferente, dependendo de quantos nós precisam ser armazenados na memória para cada implementação. Portanto, quanto menos nós tivermos que acompanhar, melhor!😊

Conclusão

Como sempre, espero que você tenha gostado do artigo e que tenha aprendido algo novo. Se quiser, você também pode seguir o autor no LinkedIn ou no Twitter.

Até logo!

O que é um algoritmo de ordenação?

Os algoritmos de ordenação são um conjunto de instruções que recebem um array ou lista como entrada e organizam os itens em uma ordem específica.

As ordenações mais comumente realizadas são a numérica ou a alfabética (também chamada de lexicográfica) e podem ser em ordem crescente (A-Z, 0-9) ou decrescente (Z-A, 9-0).

Por que algoritmos de ordenação são importantes?

Os algoritmos de ordenação são importantes em Ciência da Computação porque a ordenação pode, muitas vezes, reduzir a complexidade de um problema. Esses algoritmos têm aplicações diretas em algoritmos de busca, algoritmos de banco de dados, métodos de divisão e conquista, algoritmos de estrutura de dados e muito mais.

Vantagens e desvantagens dos algoritmos

Ao usar algoritmos diferentes, algumas perguntas devem ser feitas. Qual o tamanho da coleção que está sendo ordenada? Quanta memória está disponível para uso? A coleção precisa crescer?

As respostas a essas perguntas podem determinar qual algoritmo funcionará melhor para a situação. Alguns algoritmos como a ordenação por intercalação (merge sort, em inglês) podem precisar de muito espaço para serem executados, enquanto a ordenação por inserção nem sempre é a mais rápida, mas não requer muitos recursos para isso.

Você deve determinar quais são os requisitos do sistema e suas limitações antes de decidir qual algoritmo usar.

Algoritmos de ordenação comuns

Alguns dos algoritmos de ordenação mais comuns são:

• Selection Sort (ordenação por seleção)
• Bubble Sort
• Insertion Sort (ordenação por inserção)
• Merge Sort (ordenação por intercalação)
• Quick Sort (ordenação rápida)
• Heap Sort
• Counting Sort
• Radix Sort
• Bucket Sort

Antes de detalharmos cada um deles, contudo, vamos aprender um pouco mais sobre como são classificados os algoritmos de ordenação.

Classificação de um algoritmo de ordenação

Os algoritmos de ordenação podem ser categorizados com base nos seguintes parâmetros:

1. Baseado no número de trocas ou inversões necessários: Este é o número de vezes que o algoritmo troca os elementos para ordenar uma entrada. A ordenação por seleção requer o número mínimo de trocas.
2. Baseado no número de comparações: Este é o número de vezes que o algoritmo compara elementos para ordenar uma entrada. Usando a notação Big-O, os exemplos de algoritmos de ordenação listados acima requerem, pelo menos, O(nlogn) comparações no melhor caso e O(n^2) comparações no pior caso para a maioria das saídas.
3. Baseado no uso ou não de recursão: Alguns algoritmos, tal como Quick Sort (ordenação rápida), usa técnicas recursivas para ordenar uma entrada. Outros algoritmos de ordenação, como  Selection Sort (ordenação por seleção) ou  Insertion Sort (ordenação por inserção), usam técnicas não recursivas. Por fim, alguns algoritmos de ordenação, como  Merge Sort (ordenação por intercalação), usam tanto técnicas recursivas como não recursivas para ordenar uma entrada.
4. Baseado na estabilidade: Algoritmos de ordenação são considerados  estáveis se o algoritmo mantiver a ordem relativa dos elementos com chaves iguais. Em outras palavras, dois elementos equivalentes permanecem, após a ordenação, na mesma ordem em que estavam antes da ordenação.
   Imagine, por exemplo, que tenhamos um array de entrada [1, 2, 3, 2, 4]. Para ajudar na diferenciação entre os valores que são iguais – neste caso, os 2 – usaremos 2a e 2b, tornando o array  [1, 2a, 3, 2b, 4].
   Algoritmos de ordenação estáveis manterão a ordem de 2a e 2b. Ou seja, teremos o algoritmo ordenado [1, 2a, 2b, 3, 4]. Já os instáveis, por sua vez, não mantêm a ordem dos valores iguais, resultando em [1, 2b, 2a, 3, 4]. Insertion sort ,  Merge Sort  e  Bubble Sort são estáveis, enquanto Heap Sort  e Quick Sort não são.
5. Baseado na necessidade de espaço adicional: Alguns algoritmos podem ordenar uma lista sem criar outra inteiramente nova. Chamamos um algoritmo assim de algoritmo de ordenação  in loco e ele requer um espaço adicional O(1) constante para a ordenação. Quando os algoritmos não são in loco,  uma outra lista é criada durante a ordenação.
   Insertion sort  e  Quick sort realizam a ordenação in loco, já que os elementos são movidos em torno de um ponto fixo e não utilizam um array à parte durante o processo de ordenação.
   No Merge sort, por outro lado, o tamanho da entrada deve ser alocado de antemão para armazenar a saída durante o processo de ordenação. Isso exige um espaço adicional na memória para o processo de ordenação.

Bucket Sort

Bucket Sort é um algoritmo de ordenação por comparação que opera em elementos dividindo-os em diferentes buckets (segmentos menores de mesmo tamanho) e, em seguida, ordenando esses buckets individualmente. Cada bucket é ordenado individualmente usando um algoritmo de ordenação separado ou aplicando o algoritmo de bucket sort recursivamente.

Bucket Sort é útil principalmente quando a entrada é distribuída uniformemente em um intervalo. Por exemplo, suponhamos que tenhamos recebido um array grande de números de ponto flutuante uniformemente distribuídos entre os limites inferior e superior e precisamos ordená-lo.

Uma maneira simples de se resolver esse problema seria usar um algoritmo de ordenação, como o Merge sort, o Heap Sort ou o Quick Sort. No entanto, esses algoritmos garantem uma complexidade de tempo de, no melhor caso, O(NlogN). Usando o bucket sort, contudo, a tarefa acima pode ser concluída em tempo O(N).

Pseudocódigo para Bucket Sort:

void bucketSort(float[] a,int n)

{

    for(each floating integer 'x' in a)

    {
        insert x into bucket[n*x]; 
    }

    for(each bucket)

    {
        sort(bucket);
    }

}

Counting Sort

Counting Sort é uma técnica de ordenação baseada em chaves compreendidas em um intervalo específico. Ela funciona contando o número de objetos com valores de chave distintos (tipo de hash). Em seguida, fazendo alguma operação para calcular a posição de cada objeto na sequência de saída.

Exemplo:

Para simplificar, considere os dados no intervalo de 0 a 9. 
Dados de entrada: 1, 4, 1, 2, 7, 5, 2
  1) Use um array para armazenar a contagem de cada objeto único.
  Índice:       0  1  2  3  4  5  6  7  8  9
  Contagem:     0  2  2  0  1  1  0  1  0  0

  2) Modifique o array de contagem de modo que cada elemento em cada índice armazene a soma das contagens anteriores. 
  Índice:       0  1  2  3  4  5  6  7  8  9
  Contagem:     0  2  4  4  5  6  6  7  7  7

O array de contagem modificado indica a posição que cada objeto ocupará no array de saída.
 
  3) Posicione cada objeto do array de entrada no array de saída de modo que sua posição final seja igual ao seu valor de contagem menos 1.
  Processe os dados de entrada: 1, 4, 1, 2, 7, 5, 2. A contagem do valor (no array de contagem) é 2.
  Assim, coloque o valor 1 no índice 1 (2 - 1) do array de saída. Subtraia 1 do valor de contagem aramazenado no índice 1 do array de contagem, de modo que o próximo valor do array de entrada seja colocado em uma posição, no array de saída, igual a esse valor menos 1.
  

Propriedades

• Complexidade espacial: O(K)
• Desempenho no melhor caso: O(n+K)
• Desempenho médio: O(n+K)
• Desempenho no pior caso: O(n+K)
• Estável: Sim (K é o número de elementos distintos no array)

Implementação em JavaScript

let numbers = [1, 4, 1, 2, 7, 5, 2];
let count = [];
let i, z = 0;
let max = Math.max(...numbers);      
// inicializar o contador
for (i = 0; i <= max; i++) {
    count[i] = 0;
}
for (i=0; i < numbers.length; i++) {
    count[numbers[i]]++;
}
for (i = 0; i <= max; i++) {
    while (count[i]-- > 0) {
        numbers[z++] = i;
    }
}
// dar como resultado o array ordenado
for (i=0; i < numbers.length; i++) {
    console.log(numbers[i]);
}

Implementação em C++

#include <iostream>

void countSort(int upperBound, int lowerBound, std::vector<int> numbersToSort) //limites superior e inferior dos números no vetor
{
  int range = upperBound - lowerBound;                  //cria um intervalo grande o suficiente para obter todos os números entre o mínimo e o máximo
  std::vector<int> counts (range);                      //inicializa contagens do tamanho do intervalo
  std::fill(counts.begin(), counts.end(), 0);           //preenche os vetores com zeros
  
  for (int i = 0; i < numbersToSort.size(); i++)
  {
      int index = numbersToSort[i] - lowerBound; //Por exemplo, se 5 for o limite inferior e numberToSort[i] for 5. index será 0 e o       counts[index]+= 1;                         //contagem de 5 será armazenada em counts[0]
  }
  
  std::cout << counts << std::endl;
} 

Implementação em Swift

func countingSort(_ array: [Int]) {
  // Cria um array para armazenar a contagem de cada elemento
  let maxElement = array.max() ?? 0
  var countArray = [Int](repeating: 0, count: Int(maxElement + 1))
  
  for element in array {
    countArray[element] += 1
  }
  var z = 0
  var sortedArray = [Int](repeating: 0, count: array.count)

  for index in 1 ..< countArray.count {
    //exibe o elemento de índice o número de vezes necessárias
    while countArray[index] > 0 {
      sortedArray[z] = index
      z += 1
      countArray[index] -= 1
    }
  }
  
  print(sortedArray)
}

Insertion Sort (ordenação por inserção)

Insertion sort é um algoritmo de ordenação simples para um pequeno número de elementos.

Exemplo:

Em insertion sort, você compara o elemento  chave  com os elementos anteriores. Se os elementos anteriores são maiores do que o elemento chave, então você move o elemento anterior para a próxima posição.

Comece do índice 1 até o tamanho do array de entrada.

[ 8 3 5 1 4 2 ]

Passo 1 :

      chave = 3 //começando no índice 1.

      Aqui a `chave` será comparada com os elementos anteriores.

      Neste caso, `chave` é comparada com 8. Como 8 > 3, movemos o elemento 8 para a próxima posição e inserimos a `chave` na posição anterior.

      Resultado: [ 3 8 5 1 4 2 ]

Passo 2 :

      chave = 5 //índice 2

      8 > 5 //movemos o 8 para o índice 2 e inserimos o 5 no índice 1.

      Resultado: [ 3 5 8 1 4 2 ]

Passo 3 :

      chave = 1 //índice 3

      8 > 1     => [ 3 5 1 8 4 2 ]  

      5 > 1     => [ 3 1 5 8 4 2 ]

      3 > 1     => [ 1 3 5 8 4 2 ]

      Resultado: [ 1 3 5 8 4 2 ]

Passo 4 :

      chave = 4 //índice 4

      8 > 4   => [ 1 3 5 4 8 2 ]

      5 > 4   => [ 1 3 4 5 8 2 ]

      3 > 4   ≠>  pare

      Resultado: [ 1 3 4 5 8 2 ]

Passo 5 :

      chave = 2 //índice 5

      8 > 2   => [ 1 3 4 5 2 8 ]

      5 > 2   => [ 1 3 4 2 5 8 ]

      4 > 2   => [ 1 3 2 4 5 8 ]

      3 > 2   => [ 1 2 3 4 5 8 ]

      1 > 2   ≠> pare

      Resultado: [1 2 3 4 5 8]

O algoritmo mostrado abaixo é uma versão ligeiramente otimizada para evitar trocar o elemento chave em cada iteração. Aqui, o elemento  chave  será trocado ao final da iteração (step).

    InsertionSort(arr[])
      for j = 1 to arr.length
         key = arr[j]
         i = j - 1
         while i >= 0 and arr[i] > key
            arr[i+1] = arr[i]
            i = i - 1
         arr[i+1] = key
		

Aqui está uma implementação detalhada em JavaScript:

function insertion_sort(A) {
    var len = array_length(A);
    var i = 1;
    while (i < len) {
        var x = A[i];
        var j = i - 1;
        while (j >= 0 && A[j] > x) {
            A[j + 1] = A[j];
            j = j - 1;
        }
        A[j+1] = x;
        i = i + 1;
    }
}

Uma implementação rápida em Swift é mostrada abaixo:

  var array = [8, 3, 5, 1, 4, 2]

  func insertionSort(array:inout Array<Int>) -> Array<Int>{
      for j in 0..<array.count {
          let key = array[j]
          var i = j-1

          while (i > 0 && array[i] > key){
              array[i+1] = array[i]
              i = i-1
          }
          array[i+1] = key
      }
      return array
  }

O exemplo Java é mostrado abaixo:

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

E em  c....

void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1;
       while (j >= 0 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   } 
} 

Propriedades:

• Complexidade espacial: O(1)
• Complexidade temporal: O(n), O(n* n), O(n* n) para o melhor, médio e pior caso, respectivamente.
• Melhor caso: o array já está ordenado
• Caso médio: o array está ordenado aleatoriamente
• Pior caso: o array está ordenado em ordem inversa.
• Ordenação in loco: Sim
• Estável: Sim

Heapsort

Heapsort é um algoritmo de ordenação eficiente baseado no uso de estruturas de dados denominadas heaps (máxima/mínima). Um heap é uma estrutura de dados baseada em árvore que satisfaz a propriedade heap – ou seja, para um heap máximo, a chave de qualquer nó é menor ou igual à chave de seu pai (se tiver um pai).

Essa propriedade pode ser aproveitada para acessar o elemento máximo no heap em tempo O(logn) usando o método maxHeapify. Realizamos esta operação n vezes, cada vez movendo o elemento máximo no heap para o topo do heap e extraindo-o do heap para um array ordenado. Assim, após n iterações teremos uma versão ordenada do array de entrada.

O algoritmo exige que uma estrutura de dados heap seja construída primeiro. O algoritmo não é estável, o que significa que ao comparar objetos com a mesma chave, a ordenação original não será preservada.

Este algoritmo é executado em tempo O(nlogn) e requer espaço adicional O(1) [O(n) incluindo o espaço necessário para armazenar os dados de entrada], uma vez que todas as operações são executadas inteiramente in loco.

A complexidade de tempo melhor, pior e média do Heapsort é O(nlogn). Embora heapsort tenha uma complexidade de pior caso melhor do que o quicksort, quando bem implementado, o quicksort é executado mais rapidamente na prática. Heapsort é um algoritmo baseado em comparação, portanto, pode ser usado para conjuntos de dados não numéricos, na medida em que alguma relação (propriedade de heap) possa ser definida sobre os elementos.

Uma implementação em Java é apresentada abaixo :

import java.util.Arrays;
public class Heapsort {

	public static void main(String[] args) {
		//array de teste
		Integer[] arr = {1, 4, 3, 2, 64, 3, 2, 4, 5, 5, 2, 12, 14, 5, 3, 0, -1};
		String[] strarr = {"hope you find this helpful!", "wef", "rg", "q2rq2r", "avs", "erhijer0g", "ewofij", "gwe", "q", "random"};
		arr = heapsort(arr);
		strarr = heapsort(strarr);
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(strarr));
	}
	
	//O(nlogn) TEMPO, O(1) ESPAÇO, NÃO ESTÁVEL
	public static <E extends Comparable<E>> E[] heapsort(E[] arr){
		int heaplength = arr.length;
		for(int i = arr.length/2; i>0;i--){
			arr = maxheapify(arr, i, heaplength);
		}
		
		for(int i=arr.length-1;i>=0;i--){
			E max = arr[0];
			arr[0] = arr[i];
			arr[i] = max;
			heaplength--;
			arr = maxheapify(arr, 1, heaplength);
		}
		
		return arr;
	}
	
	//Cria maxheap a partir de um array
	public static <E extends Comparable<E>> E[] maxheapify(E[] arr, Integer node, Integer heaplength){
		Integer left = node*2;
		Integer right = node*2+1;
		Integer largest = node;
		
		if(left.compareTo(heaplength) <=0 && arr[left-1].compareTo(arr[node-1]) >= 0){
			largest = left;
		}
		if(right.compareTo(heaplength) <= 0 && arr[right-1].compareTo(arr[largest-1]) >= 0){
			largest = right;
		}	
		if(largest != node){
			E temp = arr[node-1];
			arr[node-1] = arr[largest-1];
			arr[largest-1] = temp;
			maxheapify(arr, largest, heaplength);
		}
		return arr;
	}
}

Implementação em C++

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; 
    int l = 2*i + 1;  
    int 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) 
    { 
        swap(arr[i], arr[largest]); 
  
        
        heapify(arr, n, largest); 
    } 
} 
  
 
void heapSort(int arr[], int n) 
{ 
    
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    
    for (int i=n-1; i>=0; i--) 
    { 

        swap(arr[0], arr[i]); 
  
        
        heapify(arr, i, 0); 
    } 
} 
void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Array ordenado: \n"; 
    printArray(arr, n); 
}

Radix Sort

Prerrequisito: Counting Sort

QuickSort, MergeSort e HeapSort são algoritmos de ordenação baseados em comparação. CountSort não é. Tem a complexidade de O(n+k), onde k é o elemento máximo do array de entrada. Portanto, se k é O(n), CountSort se torna ordenação linear, o que é melhor do que algoritmos de ordenação baseados em comparação que possuem complexidade de tempo O(nlogn).

A ideia é estender o algoritmo CountSort para obter uma melhor complexidade de tempo quando k for O(n2). Aí vem a ideia do Radix Sort.

O algoritmo:

Para cada dígito i onde i varia do dígito menos significativo ao dígito mais significativo de um número, ordene o array de entrada usando o algoritmo countsort de acordo com o i-ésimo dígito. Usamos a countsort porque é uma ordenação estável.

Exemplo: Suponha que o array de entrada seja:

10, 21, 17, 34, 44, 11, 654, 123

Com base no algoritmo, vamos ordenar o array de entrada de acordo com o dígito das unidades (dígito menos significativo).

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:

Assim, o array se torna 10, 21, 11, 123, 24, 44, 654, 17.

Agora, vamos ordenar de acordo com o dígito da dezena:

0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:

Agora, o array se torna: 10, 11, 17, 21, 123, 34, 44, 654.

Por fim, ordenamos de acordo com o dígito da centena (dígito mais significativo):

0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:

O array se torna: 10, 11, 17, 21, 34, 44, 123, 654, o qual está ordenado. É assim que nosso algoritmo funciona.

Uma implementação em  C:

void countsort(int arr[],int n,int place){

        int i,freq[range]={0};         //o intervalo para números inteiros é 10, pois os dígitos variam de 0 a 9
        int output[n];

        for(i=0;i<n;i++)
                freq[(arr[i]/place)%range]++;

        for(i=1;i<range;i++)
                freq[i]+=freq[i-1];
        
        for(i=n-1;i>=0;i--){
                output[freq[(arr[i]/place)%range]-1]=arr[i];
                freq[(arr[i]/place)%range]--;
        }
        
        for(i=0;i<n;i++)
                arr[i]=output[i];
}

void radixsort(ll arr[],int n,int maxx){            //maxx é o elemento máximo do array

        int mul=1;
        while(maxx){
                countsort(arr,n,mul);
                mul*=10;
                maxx/=10;
        }
}

Selection Sort

Selection Sort é um dos algoritmos de ordenação mais simples. Esse algoritmo recebe seu nome pela maneira como ele percorre o array ao longo das iterações: ele seleciona o menor elemento atual e o troca de lugar.

Veja como funciona:

1. Encontre o menor elemento no array e troque-o de lugar com o primeiro elemento.
2. Encontre o segundo menor elemento e troque com o segundo elemento no array.
3. Encontre o terceiro menor elemento e troque com o terceiro elemento no array.
4. Repita o processo de encontrar o próximo menor elemento e trocá-lo na posição correta até que todo o array esteja ordenado.

Mas, como você escreveria o código para encontrar o índice do segundo menor valor em um array?

Uma maneira fácil é notar que o menor valor já foi trocado para o índice 0, então o problema se reduz a encontrar o menor elemento no array começando no índice 1.

A ordenação por seleção sempre leva o mesmo número de comparações de chave — N(N − 1)/2.

Implementação em C/C++

O programa C++ a seguir contém uma implementação iterativa e recursiva do algoritmo Selection Sort. Ambas implementações são invocadas na função main().

#include <iostream>
#include <string>
using namespace std;

template<typename T, size_t n>
void print_array(T const(&arr)[n]) {
    for (size_t i = 0; i < n; i++)
        std::cout << arr[i] << ' ';
    cout << "\n";
}

int minIndex(int a[], int i, int j) {
    if (i == j)
        return i;
    int k = minIndex(a, i + 1, j);
    return (a[i] < a[k]) ? i : k;
}

void recurSelectionSort(int a[], int n, int index = 0) {
    if (index == n)
        return;
    int k = minIndex(a, index, n - 1);
    if (k != index)
        swap(a[k], a[index]);
    recurSelectionSort(a, n, index + 1);
}

void iterSelectionSort(int a[], int n) {
    for (int i = 0; i < n; i++)
    {
        int min_index = i;
        int min_element = a[i];
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < min_element)
            {
                min_element = a[j];
                min_index = j;
            }
        }
        swap(a[i], a[min_index]);
    }
}

int main() {
    int recurArr[6] = { 100,35, 500, 9, 67, 20 };
    int iterArr[5] = { 25, 0, 500, 56, 98 };

    cout << "Selection Sort Recursivo"  << "\n";
    print_array(recurArr); // 100 35 500 9 67 20
    recurSelectionSort(recurArr, 6);
    print_array(recurArr); // 9 20 35 67 100 500

    cout << "Selection Sort Iterativo" << "\n";
    print_array(iterArr); // 25 0 500 56 98
    iterSelectionSort(iterArr, 5);
    print_array(iterArr); // 0 25 56 98 500
}

Implementação em JavaScript

function selection_sort(A) {
    var len = A.length;
    for (var i = 0; i < len - 1; i = i + 1) {
        var j_min = i;
        for (var j = i + 1; j < len; j = j + 1) {
            if (A[j] < A[j_min]) {
                j_min = j;
            } else {}
        }
        if (j_min !== i) {
            swap(A, i, j_min);
        } else {}
    }
}

function swap(A, x, y) {
    var temp = A[x];
    A[x] = A[y];
    A[y] = temp;
}

Implementação em Python

def selection_sort(arr):
    if not arr:
        return arr
    for i in range(len(arr)):
        min_i = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_i]:
                min_i = j
        arr[i], arr[min_i] = arr[min_i], arr[i]

Implementação em Java

public void selectionsort(int array[])
{
    int n = array.length;            //método para calcular o tamanho do array 
    for (int i = 0; i < n-1; i++)
    {
        int index = i;
        int min = array[i];          // tomando o elemento min como i-ésimo elemento do array
        for (int j = i+1; j < n; j++)
        {
            if (array[j] < array[index])
            {
                index = j;
                min = array[j];
            }
        }
        int t = array[index];         //Troque os elementos de lugar
        array[index] = array[i];
        array[i] = t;
    }
}

Implementação em MATLAB

function [sorted] = selectionSort(unsorted)
    len = length(unsorted);
    for i = 1:1:len
        minInd = i;
        for j = i+1:1:len
           if unsorted(j) < unsorted(minInd) 
               minInd = j;
           end
        end
        unsorted([i minInd]) = unsorted([minInd i]);    
    end
    sorted = unsorted;
end

Propriedades

• Complexidade espacial:  O(n)
• Complexidade temporal:  O(n2)
• Ordenação in loco:  Sim
• Estável:  Não

Bubble Sort

Assim como as bolhas sobem do fundo de um copo, bubble sort é um algoritmo simples que ordena uma lista, permitindo que valores mais baixos ou mais altos borbulhem até o topo. O algoritmo percorre uma lista e compara valores adjacentes, trocando-os se não estiverem na ordem correta.

Com uma complexidade de pior caso de O(n^2), a ordenação por bolhas é muito lenta em comparação com outros algoritmos de ordenação como o quicksort. A vantagem é que é um dos algoritmos de ordenação mais fáceis de entender e implementar do zero.

Do ponto de vista técnico, o bubble sort é razoável para ordenar arrays de tamanho pequeno ou, especialmente, ao executar algoritmos de ordenação em computadores com recursos de memória notavelmente limitados.

Exemplo:

Primeira passagem pela lista:

• Começando com [4, 2, 6, 3, 9], o algoritmo compara os dois primeiros elementos no array, 4 e 2. Ele os troca porque 2 < 4: [2, 4, 6, 3, 9]
• Ele compara os dois próximos valores, 4 e 6. Como 4 < 6, e estes já estão em ordem, o algoritmo segue em frente: [2, 4, 6, 3, 9]
• Os próximos dois valores são trocados, porque 3 < 6: [2, 4, 3, 6, 9]
• Os dois últimos valores, 6 e 9, já estão em ordem, então o algoritmo não os troca.

Segunda passagem pela lista:

• 2 < 4, então não há necessidade de trocar as posições: [2, 4, 3, 6, 9]
• O algoritmo troca os próximos dois valores, porque 3 < 4: [2, 3, 4, 6, 9]
• Sem trocas, porque 4 < 6: [2, 3, 4, 6, 9]
• Novamente, 6 < 9, logo, nenhuma troca ocorre: [2, 3, 4, 6, 9]

A lista já está ordenada, mas o algoritmo bubble sort não percebe isso. Em vez disso, ele precisa concluir uma passagem inteira pela lista sem trocar nenhum valor para saber que a lista está ordenada.

Terceira passagem pela lista:

• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]
• [2, 4, 3, 6, 9] => [2, 4, 3, 6, 9]

Claramente bubble sort está longe de ser o algoritmo de ordenação mais eficiente. Ainda assim, é simples entender e implementar você mesmo.

Propriedades

• Complexidade espacial: O(1)
• Performance no melhor caso: O(n)
• Performance no caso médio: O(n*n)
• Performance no pior caso: O(n*n)
• Estável: Sim

Explicação em vídeo

Bubble sort algorithm (em inglês)

Exemplo em JavaScript

let arr = [1, 4, 7, 45, 7,43, 44, 25, 6, 4, 6, 9],
    sorted = false;

while(!sorted) {
  sorted = true;
  for(var i=0; i < arr.length; i++) {
    if(arr[i] < arr[i-1]) {
      let temp = arr[i];
      arr[i] = arr[i-1];
      arr[i-1] = temp;
      sorted = false;
    }
  }
}

Exemplo em Java

public class BubbleSort {
    static void sort(int[] arr) {
        int n = arr.length;
        int temp = 0;
         for(int i=0; i < n; i++){
                 for(int x=1; x < (n-i); x++){
                          if(arr[x-1] > arr[x]){
                                 temp = arr[x-1];
                                 arr[x-1] = arr[x];
                                 arr[x] = temp;
                         }

                 }
         }

    }
    public static void main(String[] args) {

		for(int i=0; i < 15; i++){
			int arr[i] = (int)(Math.random() * 100 + 1);
		}

                System.out.println("array before sorting\n");
                for(int i=0; i < arr.length; i++){
                        System.out.print(arr[i] + " ");
                }
                bubbleSort(arr);
                System.out.println("\n array after sorting\n");
                for(int i=0; i < arr.length; i++){
                        System.out.print(arr[i] + " ");
                }

        }
}

Exemplo em C++

// Implementação por recursão
void bubblesort(int arr[], int n)
{
	if(n==1)	//Caso inicial
		return;
	bool swap_flag = false;
	for(int i=0;i<n-1;i++)	//Após essa passada, o elemento maior é movido para o local desejado.
	{
		if(arr[i]>arr[i+1])
		{
			int temp=arr[i];
			arr[i]=arr[i+1];
			arr[i+1]=temp;
			swap_flag = true;
		}
	}
        // Se não houver a troca de dois elementos no laço, retorna, pois o array está ordenado
	if(swap_flag == false)
		return;
	bubblesort(arr,n-1);	//Recursão para o restante do array
}

Exemplo em Swift

func bubbleSort(_ inputArray: [Int]) -> [Int] {
    guard inputArray.count > 1 else { return inputArray } // Garantir que nosso array de entrada tem mais de 1 elemento
    var numbers = inputArray // Argumentos de função são constantes por padrão em Swift, então fazemos uma cópia
    for i in 0..<(numbers.count - 1) {
        for j in 0..<(numbers.count - i - 1) {
            if numbers[j] > numbers[j + 1] {
                numbers.swapAt(j, j + 1)
            }
        }
    }
    return numbers // retorna o array ordenado
} 

Exemplo em Python

def bubbleSort(arr): 
    n = len(arr) 
    for i in range(n):
        for j in range(0, n-i-1):
                if arr[j] > arr[j+1] : 
                        arr[j], arr[j+1] = arr[j+1], arr[j]
    print(arr)

Exemplo em PHP

function bubble_sort($arr) {
    $size = count($arr)-1;
    for ($i=0; $i<$size; $i++) {
        for ($j=0; $j<$size-$i; $j++) {
            $k = $j+1;
            if ($arr[$k] < $arr[$j]) {
                // Troca os elementos nos índices: $j, $k
                list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]);
            }
        }
    }
    return $arr;// retorna o array ordenado
}

$arr = array(1,3,2,8,5,7,4,0);
print("Before sorting");
print_r($arr);

$arr = bubble_sort($arr);
print("After sorting by using bubble sort");
print_r($arr);

Exemplo em C

#include <stdio.h>

int BubbleSort(int array[], int n);

int main(void) {
  int arr[] = {10, 2, 3, 1, 4, 5, 8, 9, 7, 6};
  BubbleSort(arr, 10);

  for (int i = 0; i < 10; i++) {
    printf("%d", arr[i]);
  }
  return 0;
}
int BubbleSort(int array[], n)
{
for (int i = 0 ; i < n - 1; i++)
  {
    for (int j = 0 ; j < n - i - 1; j++)     //n é o tamanho do array
    {
      if (array[j] > array[j+1])      // Para o uso com ordem decrescente 
      {
        int swap   = array[j];
        array[j]   = array[j+1];
        array[j+1] = swap;
      }
    }
  }
}

Quick Sort

Quick sort é um eficiente algoritmo de ordenação que emprega a técnica de divisão e conquista. A complexidade temporal no caso médio do Quick Sort é O(nlog(n)), sendo O(n^2) no pior caso dependendo da seleção do elemento pivô, que divide o array atual em dois subarrays.

Por exemplo, a complexidade de tempo do Quick Sort é aproximadamente O(nlog(n)) quando a seleção do pivô divide o array original em dois sub arrays de tamanhos quase iguais.

Por outro lado, se o algoritmo, que seleciona o elemento pivô dos arrays de entrada, produz consistentemente 2 sub-arrays com uma grande diferença em termos de tamanho, o algoritmo de ordenação rápida pode atingir a complexidade temporal de pior caso de O(n^2 ).

As etapas envolvidas no Quick Sort são:

• Escolha um elemento para servir como pivô, neste caso, o último elemento do array é o pivô.
• Particionamento: Ordene o array de forma que todos os elementos menores que o pivô fiquem à esquerda e todos os elementos maiores que o pivô fiquem à direita.
• Execute o algoritmo recursivamente, levando em consideração o pivô anterior para subdividir adequadamente os arrays esquerdo e direito. (Uma explicação mais detalhada pode ser encontrada nos comentários abaixo)

Exemplos de implementação em várias linguagens

Implementação em JavaScript:

const arr = [6, 2, 5, 3, 8, 7, 1, 4];

const quickSort = (arr, start, end) => {

  if(start < end) {

    // Você pode aprender sobre como o valor do pivô é derivado nos comentários abaixo
    let pivot = partition(arr, start, end);

    // Certifique-se de ler os comentários abaixo para entender por que pivô - 1 e pivô + 1 são usados
    // Estas são as chamadas recursivas do quickSort
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
  } 

}

const partition = (arr, start, end) => { 
  let pivot = end;
  // Defina i como start - 1 para que ele possa acessar o primeiro índice no caso de o valor em arr[0] ser maior que arr[pivot]
  // Os comentários abaixo explicarão o comentário acima
  let i = start - 1,
      j = start;

  // Incrementar j até o índice anterior ao pivô
  while (j < pivot) {

    // If the value is greater than the pivot increment j
    if (arr[j] > arr[pivot]) {
      j++;
    }

    // Quando o valor em arr[j] for menor que o pivô:
    // incremente i (arr[i] será um valor maior que arr[pivot]) e troque o valor em arr[i] e arr[j]
    else {
      i++;
      swap(arr, j, i);
      j++;
    }

  }

  //O valor em arr[i + 1] será maior que o valor de arr[pivot]
  swap(arr, i + 1, pivot);

  //Você retorna i + 1, pois os valores à esquerda dele são menores que arr[i+1], e os valores à direita são maiores que arr[i + 1]
  // Dessa forma, quando os quicksorts recursivos são chamados, os novos sub-arrays não incluirão este valor pivô usado anteriormente
  return i + 1;
}

const swap = (arr, firstIndex, secondIndex) => {
  let temp = arr[firstIndex];
  arr[firstIndex] = arr[secondIndex];
  arr[secondIndex] = temp;
}

quickSort(arr, 0, arr.length - 1);
console.log(arr);

Implementação em C

#include<stdio.h>  
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
}
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];     
    int i = (low - 1);  
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (arr[j] <= pivot) 
        { 
            i++;    
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
}
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    {
        int pi = partition(arr, low, high); 
  
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 
  

void printArray(int arr[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("n"); 
} 
  

int main() 
{ 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    quickSort(arr, 0, n-1); 
    printf("Sorted array: n"); 
    printArray(arr, n); 
    return 0; 
} 

Implementação em Python3

import random

z=[random.randint(0,100) for i in range(0,20)]

def quicksort(z):
    if(len(z)>1):        
        piv=int(len(z)/2)
        val=z[piv]
        lft=[i for i in z if i<val]
        mid=[i for i in z if i==val]
        rgt=[i for i in z if i>val]

        res=quicksort(lft)+mid+quicksort(rgt)
        return res
    else:
        return z
        
ans1=quicksort(z)
print(ans1)

Implementação em MATLAB

a = [9,4,7,3,8,5,1,6,2];

sorted = quicksort(a,1,length(a));

function [unsorted] =  quicksort(unsorted, low, high)
    if low < high
        [pInd, unsorted] = partition(unsorted, low, high);
        unsorted = quicksort(unsorted, low, pInd-1);
        unsorted = quicksort(unsorted, pInd+1, high);
    end

end

function [pInd, unsorted] = partition(unsorted, low, high)
    i = low-1;
    for j = low:1:high-1
        if unsorted(j) <= unsorted(high)
            i = i+1;
            unsorted([i,j]) = unsorted([j,i]);
            
        end
    end
    unsorted([i+1,high]) = unsorted([high,i+1]);
    pInd = i+1;

end

A complexidade espacial do quick sort é  O(n) . Esta é uma melhoria em relação a outros algoritmos de ordenação de divisão e conquista, que têm complexidade espacial de  O(nlong(n)).

Quick sort consegue isso alterando a ordem dos elementos dentro de um determinado array. Compare isso com o algoritmo merge sort que cria 2 arrays, cada um com tamanho n/2, a cada chamada da função.

No entanto existe o problema deste algoritmo de ordenação ser de tempo O(n*n)  se o pivô é sempre mantido no meio. Um problema que pode ser contornado utilizando-se um pivô aleatório

Complexidade

O uso de memória no melhor, médio e pior caso corresponde a n log(n)n, log(n)n e 2log(n) respectivamente. It's not a stable algorithm, and quicksort is usually done in-place with O(log(n)) stack space.

A complexidade espacial do quick sort é O(n). Esta é uma melhoria em relação a outros algoritmos de ordenação de divisão e conquista, que ocupam espaço O(n log(n)).

Timsort

Timsort é um algoritmo de ordenação rápido que trabalha com complexidade O(N log(N)) estável.

Timsort é uma mistura de Insertion Sort e Mergesort. Esse algoritmo é implementado no método Arrays.sort() em Java, bem como nas funções sorted() e sort() em Python. As partes menores são ordenadas usando o Insertion Sort e posteriormente mescladas usando Mergesort.

Uma rápida implementação em Python:

def binary_search(the_array, item, start, end):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end)/ 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:
        return binary_search(the_array, item, start, mid - 1)

    else:
        return mid

"""
Insertion sort utilizada pelo timsort se o tamanho do array ou da "run" é pequeno.
"""
def insertion_sort(the_array):
    l = len(the_array)
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
    return the_array

def merge(left, right):
    """Recebe duas listas ordenadas e retorna uma única lista ordenada comparando os elementos um de cada vez.
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

def timsort(the_array):
    runs, sorted_runs = [], []
    length = len(the_array)
    new_run = [the_array[0]]

    # Para cada i no intervalo de 1 até o tamanho do array
    for i in range(1, length):
        #se i está no final da lista
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break
        # se o i-ésimo elemento do array for menor que o anterior
        if the_array[i] < the_array[i-1]:
            # se new_run estiver definido como None (nulo)
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        # senão se for igual ou maior que
        else:
            new_run.append(the_array[i])

    # para cada item em runs, adicione o item usando insertion sort
    for item in runs:
        sorted_runs.append(insertion_sort(item))
    
    # para cada run em sorted_runs, mescle-as
    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    print(sorted_array)

timsort([2, 3, 1, 5, 6, 7])

Complexidade:

Tim sort tem uma complexidade estável de O(N log(N)) e se compara muito bem com Quicksort. Uma comparação de complexidades pode ser encontrada neste gráfico.

Merge Sort

Merge Sort é um algoritmo que emprega a técnica de divisão e conquista. Ele divide o array de entrada em duas metades, chama a si mesmo pelas duas metades e depois mescla as duas metades já ordenadas. A maior parte do algoritmo recebe dois arrays ordenados, e temos que mesclá-los em um único array ordenado. Todo o processo de ordenação de um array de N inteiros pode ser resumido em três etapas:

• Dividir o array em duas metades.
• Ordene a metade esquerda e a metade direita usando o mesmo algoritmo recursivamente.
• Mescle as metades ordenadas.

Existe um algoritmo chamado Two Finger Algorithm que nos ajuda a mesclar dois arrays ordenados. Usar essa sub-rotina e chamar a função merge sort nas metades do array recursivamente nos dará o array ordenado final que estamos procurando.

Como este é um algoritmo baseado em recursão, temos uma relação de recorrência para ele. Uma relação de recorrência é simplesmente uma maneira de representar um problema em termos de seus subproblemas.

T(n) = 2 * T(n / 2) + O(n)

Colocando em linguagem simples, dividimos o subproblema em duas partes em cada etapa e temos uma quantidade linear de trabalho que precisamos realizar para mesclar as duas metades ordenadas em cada etapa.

Complexidade

A maior vantagem de usar Merge sort é que a complexidade temporal é apenas n*log(n) para ordenar um array inteiro. É muito melhor do que a complexidade temporal de n^2 de execução de bubble sort ou insertion sort.

Antes de escrevermos o código, vamos entender como a ordenação por mesclagem funciona com a ajuda de um diagrama.

• Inicialmente temos um array de 6 inteiros não ordenados Arr(5, 8, 3, 9, 1, 2)
• Dividimos o array em duas metades Arr1 = (5, 8, 3) e Arr2 = (9, 1, 2).
• Novamente, nós os dividimos em duas metades: Arr3 = (5, 8) e Arr4 = (3) e Arr5 = (9, 1) e Arr6 = (2).
• Novamente, nós os dividimos em duas metades: Arr7 = (5), Arr8 = (8), Arr9 = (9), Arr10 = (1) e Arr6 = (2).
• Vamos agora comparar os elementos nesses sub-arrays para mesclá-los.

Propriedades:

• Complexidade espacial: O(n)
• Complexidade temporal: O(n*log(n)). A complexidade temporal para o Merge Sort pode não ser óbvia à primeira vista. O fator log(n) entra por causa da relação de recorrência que mencionamos anteriormente.
• Ordenação in-loco: Não em uma implementação típica
• Estável: Sim
• Paralelizável :sim (diversas variantes paralelas são discutidas na terceira edição do livro Introduction to Algorithms Cormen de Leiserson, Rivest, and Stein.)

Implementação em C++

void merge(int array[], int left, int mid, int right)
{
    int i, j, k;

    // tamanho do sub-array esquerdo
int size_left = mid - left + 1;

// tamanho do sub-array direito
int size_right =  right - mid;

/* Criar arrays temporários */
int Left[size_left], Right[size_right];

/* Copiar dados para os arrays temporários L[] e R[] */
for(i = 0; i < size_left; i++)
{
    Left[i] = array[left+i];
}

for(j = 0; j < size_right; j++)
{
    Right[j] = array[mid+1+j];
}

// Mesclar os arrays temporários de volta no arr[left..right]
i = 0; // índice inicial do sub-array esquerdo
j = 0; // índice inicial do sub-array direito
k = left; // índice inicial do array mesclado

while (i < size_left && j < size_right)
{
    if (Left[i] <= Right[j])
    {
        array[k] = Left[i];
        i++;
    }
    else
    {
        array[k] = Right[j];
        j++;
    }
    k++;
}

// Copiar os elementos restantes de Left[]
while (i < size_left)
{
    array[k] = Left[i];
    i++;
    k++;
}

// Copiar os elementos restantes de R[]
while (j < size_right)
{
    array[k] = Right[j];
    j++;
    k++;
}
}

void mergeSort(int array[], int left, int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;

        // Ordenar a primeira e a segunda metade
    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);

    // Finalmente, mesclá-las
    merge(array, left, mid, right);
}
}

Implementação em JavaScript

function mergeSort (arr) {
  if (arr.length < 2) return arr;
  var mid = Math.floor(arr.length /2);
  var subLeft = mergeSort(arr.slice(0,mid));
  var subRight = mergeSort(arr.slice(mid));
  return merge(subLeft, subRight);
}

Primeiro, verificamos o comprimento do array. Se for 1, simplesmente retornamos o array. Este seria o nosso caso base. Caso contrário, descobriremos o valor do meio e dividiremos o array em duas metades. Agora vamos ordenar ambas metades com chamadas recursivas da função MergeSort.

function merge (a,b) {
    var result = [];
    while (a.length >0 && b.length >0)
        result.push(a[0] < b[0]? a.shift() : b.shift());
    return result.concat(a.length? a : b);
}

Quando mesclamos as duas metades, armazenamos o resultado em um array auxiliar. Vamos comparar o elemento inicial do array esquerdo com o elemento inicial do array direito. O que for menor será enviado para o array de resultados e o removeremos dos respectivos arrays usando o operador [shift() . Se ainda restarem valores no array esquerdo ou direito, simplesmente o concatenamos no final do resultado. Aqui está o resultado ordenado:

var test = [5,6,7,3,1,3,15];
console.log(mergeSort(test));

>> [1, 3, 3, 5, 6, 7, 15]

Um tutorial sobre Merge Sort no YouTube

Aqui está um bom vídeo do YouTube que aborda o tópico em detalhes (em inglês).

Implementação em JS

const list = [23, 4, 42, 15, 16, 8, 3]

const mergeSort = (list) =>{
  if(list.length <= 1) return list;
  const middle = list.length / 2 ;
  const left = list.slice(0, middle);
  const right = list.slice(middle, list.length);
  return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
  var result = [];
  while(left.length || right.length) {
    if(left.length && right.length) {
      if(left[0] < right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    } else if(left.length) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
  return result;
}

console.log(mergeSort(list)) // [ 3, 4, 8, 15, 16, 23, 42 ]

Implementação em C

#include<stdlib.h> 
#include<stdio.h>
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    
    int L[n1], R[n2]; 
  
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j];
    i = 0; 
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    {  
        int m = l+(r-l)/2; 
  
        
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
}
void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
  
    printf("Given array is \n"); 
    printArray(arr, arr_size); 
  
    mergeSort(arr, 0, arr_size - 1); 
  
    printf("\nSorted array is \n"); 
    printArray(arr, arr_size); 
    return 0; 

Implementação em C++

Vamos considerar o array A = {2,5,7,8,9,12,13} e array B = {3,5,6,9,15} e queremos que o array C esteja ordenado em ordem crescente também.

void mergesort(int A[],int size_a,int B[],int size_b,int C[])
{
     int token_a,token_b,token_c;
     for(token_a=0, token_b=0, token_c=0; token_a<size_a && token_b<size_b; )
     {
          if(A[token_a]<=B[token_b])
               C[token_c++]=A[token_a++];
          else
               C[token_c++]=B[token_b++];
      }
      
      if(token_a<size_a)
      {
          while(token_a<size_a)
               C[token_c++]=A[token_a++];
      }
      else
      {
          while(token_b<size_b)
               C[token_c++]=B[token_b++];
      }

}

Implementação em Python

def merge(left,right,compare):
	result = [] 
	i,j = 0,0
	while (i < len(left) and j < len(right)):
		if compare(left[i],right[j]):
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	while (i < len(left)):
		result.append(left[i])
		i += 1
	while (j < len(right)):
		result.append(right[j])
		j += 1
	return result

def merge_sort(arr, compare = lambda x, y: x < y):
     #Função lambda usada para ordenar um array em ordem crescente e decrescente.
     #Por padrão, ela ordena o array em ordem crescente
	if len(arr) < 2:
		return arr[:]
	else:
		middle = len(arr) // 2
		left = merge_sort(arr[:middle], compare)
		right = merge_sort(arr[middle:], compare)
		return merge(left, right, compare) 

arr = [2,1,4,5,3]
print(merge_sort(arr))

Implementação em Java

public class mergesort {

	public static int[] mergesort(int[] arr,int lo,int hi) {
		
		if(lo==hi) {
			int[] ba=new int[1];
			ba[0]=arr[lo];
			return ba;
		}
		
		int mid=(lo+hi)/2;
		int arr1[]=mergesort(arr,lo,mid);
		int arr2[]=mergesort(arr,mid+1,hi);
		return merge(arr1,arr2);
	}
	
	public static int[] merge(int[] arr1,int[] arr2) {
		int i=0,j=0,k=0;
		int n=arr1.length;
		int m=arr2.length;
		int[] arr3=new int[m+n];
		while(i<n && j<m) {
			if(arr1[i]<arr2[j]) {
				arr3[k]=arr1[i];
				i++;
			}
			else {
				arr3[k]=arr2[j];
				j++;
			}
			k++;
		}
		
		while(i<n) {
			arr3[k]=arr1[i];
			i++;
			k++;
		}
		
		while(j<m) {
			arr3[k]=arr2[j];
			j++;
			k++;
		}
		
		return arr3;
		
	}
	
	public static void main(String[] args) {
		int arr[]= {2,9,8,3,6,4,10,7};
		int[] so=mergesort(arr,0,arr.length-1);
		for(int i=0;i<arr.length;i++)
			System.out.print(so[i]+" ");
	}

}

Boas-vindas! Se você sempre quis aprender e entender o algoritmo de Dijkstra, este artigo é para você. Você verá como ele funciona nos bastidores com uma explicação gráfica passo a passo.

Você aprenderá:

• Conceitos básicos sobre grafos (uma breve revisão).
• Para que o algoritmo de Dijkstra é utilizado.
• Como o algoritmo funciona através de um exemplo passo a passo.

Vamos começar. ✨

🔹 Introdução aos grafos

Vamos começar com uma breve introdução aos grafos.

Conceitos básicos

Grafos são estruturas de dados usadas para representar "conexões" entre pares de elementos.

• Esses elementos são chamados de nós (ou vértices). Eles representam objetos, pessoas ou entidades da vida real.
• As conexões entre os nós são chamadas de arestas.

Esta é uma representação gráfica de um grafo:

Os nós são representados por círculos coloridos e as arestas são representadas por linhas que conectam esses círculos.

💡 Dica: dois nós estarão conectados se houver uma aresta entre eles.

Aplicações

Os grafos são diretamente aplicáveis a cenários do mundo real. Por exemplo, poderíamos usá-los para modelar uma rede de transporte, onde os nós representariam instalações que enviam ou recebem produtos e arestas representariam estradas ou caminhos que os conectam (veja abaixo).

Tipos de grafos

Os grafos podem ser:

• Não dirigidos: se para cada par de nós conectados, você pode ir de um nó para o outro em ambas as direções.
• Dirigidos: se para cada par de nós conectados, você só pode ir de um nó para outro em uma direção específica. Usamos setas em vez de linhas simples para representar arestas dirigidas.

💡 Dica: neste artigo, abordaremos grafos não dirigidos.

Grafos ponderados

Um grafo ponderado é um grafo cujas arestas têm um "peso" ou "custo". O peso de uma aresta pode representar distância, tempo ou qualquer coisa que modele a "conexão" entre o par de nós que ela conecta.

Por exemplo, no grafo ponderado abaixo, você pode ver um número em azul próximo de cada aresta. Este número é usado para representar o peso da aresta correspondente.

💡 Dica: esses pesos são essenciais para o Algoritmo de Dijkstra. Você verá por que a seguir.

🔸 Introdução ao algoritmo de Dijkstra

Agora que você conhece os conceitos básicos de grafos, vamos nos aprofundar nesse algoritmo incrível.

• Propósito e casos de uso
• História
• Elementos básicos do algoritmo
• Requisitos

Propósito e casos de uso

Com o algoritmo de Dijkstra, você poderá encontrar o caminho de menor custo entre nós em um grafo. Particularmente, você poderá encontrar o caminho de menor custo entre um nó (denominado “origem”) e todos os outros nós do grafo, produzindo uma árvore de custo-mínimo.

Este algoritmo é usado em dispositivos GPS para encontrar o caminho mais curto entre a localização atual e o destino. Ele possui ampla aplicação na indústria, principalmente em domínios que requerem modelagem de redes

História

Este algoritmo foi criado e publicado pelo Dr. Edsger W. Dijkstra, um brilhante cientista da computação e engenheiro de software holandês.

Em 1959, ele publicou um artigo de 3 páginas intitulado "A note on two problems in connexion with graphs" (Uma nota sobre dois problemas em conexão com grafos, em tradução livre), onde explicou seu novo algoritmo.

Durante uma entrevista em 2001, o dr. Dijkstra revelou como e por que desenvolveu o algoritmo:

Qual é o caminho mais curto para viajar de Roterdã a Groningen? É o algoritmo para o caminho mais curto, que projetei em aproximadamente 20 minutos. Certa manhã, eu estava fazendo compras em Amsterdã com minha noiva e, cansado, sentamos no terraço do café para beber uma xícara de café e eu estava pensando se poderia fazer isso, e então, desenvolvi o algoritmo para o caminho mais curto . Como eu disse, foi uma invenção de 20 minutos. Na verdade, foi publicado em 1959, três anos depois. A publicação continua bem legal. Uma das razões por que ela é tão legal foi que eu a desenhei sem lápis e papel. Sem lápis e papel, você é quase forçado a evitar todas as complexidades evitáveis. Eventualmente, esse algoritmo se tornou, para minha grande surpresa, um dos pilares da minha fama. — Conforme citado no artigo Edsger W. Dijkstra em An interview with Edsger W. Dijkstra (Uma entrevista com Edsger W. Dijkstra).

⭐ Inacreditável, não? Em apenas 20 minutos, o Dr. Dijkstra desenvolveu um dos algoritmos mais famosos da história da Ciência da Computação.

Noções básicas do algoritmo de Dijkstra

• O Algoritmo de Dijkstra basicamente começa no nó que você escolhe (o nó de origem) e analisa o grafo para encontrar o caminho de menor custo entre esse nó e todos os outros nós do grafo.
• O algoritmo mantém o registro da distância mais curta atualmente conhecida de cada nó até o nó de origem e atualiza esses valores se encontrar um caminho de menor custo.
• Uma vez que o algoritmo encontrou o caminho de menor custo entre o nó de origem e outro nó, esse nó é marcado como "visitado" e adicionado ao caminho.
• O processo continua até que todos os nós do grafo tenham sido adicionados ao caminho. Desta forma, temos um caminho que conecta o nó de origem a todos os outros nós seguindo o caminho de menor custo possível para chegar a cada nó.

Requisitos

O Algoritmo de Dijkstra só funciona com grafos com pesos positivos. Isso porque, durante o processo, os pesos das arestas devem ser somados para encontrar o caminho de menor custo.

Se houver um peso negativo no grafo, o algoritmo não funcionará corretamente. Uma vez que um nó tenha sido marcado como "visitado", o caminho atual para esse nó é marcado como o caminho de menor custo para chegar a esse nó. E pesos negativos podem alterar isso se o peso total puder ser decrementado após essa etapa ter ocorrido.

🔹 Exemplo do algoritmo de Dijkstra

Agora que você sabe mais sobre esse algoritmo, vamos ver como ele funciona nos bastidores com um exemplo passo a passo.

Temos este grafo:

O algoritmo gerará o caminho de menor custo (neste caso, o caminho mais curto) do nó 0 para todos os outros nós do grafo.

💡 Dica: neste caso, assumiremos que o peso das arestas representa a distância entre dois nós.

Teremos o caminho mais curto do nó 0 ao nó 1, do nó 0 ao nó 2, do nó 0 ao nó 3, e assim por diante para cada nó do grafo.

Inicialmente, temos esta lista de distâncias (veja a lista abaixo):

• A distância do nó de origem até ele mesmo é 0. Para este exemplo, o nó de origem será o nó 0, mas pode ser qualquer nó que você escolher.
• A distância do nó de origem para todos os outros nós ainda não foi determinada, então usamos o símbolo do infinito para representar isso inicialmente.

Também temos esta lista (veja abaixo) para acompanhar os nós que ainda não foram visitados (nós que não foram incluídos no caminho):

💡 Dica: lembre-se de que o algoritmo é concluído quando todos os nós forem adicionados ao caminho.

Como estamos escolhendo começar no nó 0, podemos marcar esse nó como visitado. De forma equivalente, nós o cortamos da lista de nós não visitados e adicionamos uma borda vermelha ao nó correspondente no diagrama:

Agora precisamos verificar a distância do nó 0 até seus nós adjacentes. Como você pode ver, estes são os nós  1 e 2 (veja as bordas vermelhas):

💡 Dica: isso não significa que estamos adicionando imediatamente os dois nós adjacentes ao caminho mais curto. Antes de adicionar um nó a este caminho, precisamos verificar se encontramos o caminho mais curto para alcançá-lo. Estamos simplesmente fazendo um processo de exame inicial para ver as opções disponíveis.

Precisamos atualizar as distâncias do nó 0 ao 1 e ao nó 2 com os pesos das arestas que os conectam ao nó 0 (origem). Estes pesos são 2 e 6, respectivamente:

Após atualizar as distâncias dos nós adjacentes, precisamos:

• Selecionar o nó mais próximo do nó de origem com base nas distâncias conhecidas atuais.
• Marcá-lo como visitado.
• Adicioná-lo ao caminho.

Se verificarmos a lista de distâncias, podemos ver que o nó 1 tem a menor distância até a origem (distância igual a 2), então, nós o adicionamos ao caminho.

No diagrama, podemos representar isso com uma aresta vermelha:

Marcamos com um quadrado vermelho na lista para representar que foi "visitado" e que encontramos o caminho mais curto para este nó:

Riscamos da lista de nós não visitados:

Agora, precisamos analisar os novos nós adjacentes para encontrar o caminho mais curto para alcançá-los. Analisaremos apenas os nós que são adjacentes aos nós que já fazem parte do caminho mais curto (o caminho marcado com arestas vermelhas).

Os nós 3 e 2 são ambos adjacentes aos nós que já estão no caminho porque estão diretamente conectados aos nós1 e 0, respectivamente, como você pode ver abaixo. Esses são os nós que analisaremos na próxima etapa.

Como já temos a distância do nó de origem ao nó 2 anotado em nossa lista, não precisamos atualizar a distância desta vez. Precisamos apenas atualizar a distância do nó de origem ao novo nó adjacente (o nó 3):

Essa distância é igual a 7. Vamos ver o porquê.

Para encontrar a distância do nó de origem para outro nó (neste caso, nó 3), somamos os pesos de todas as arestas que formam o caminho mais curto para chegar a esse nó:

• No caso do nó 3: a distância total é 7 porque adicionamos os pesos das arestas que formam o caminho0 -> 1 -> 3 (2  para a aresta 0 -> 1 e 5 para a aresta 1 -> 3).

Agora que temos a distância até os nós adjacentes, temos que escolher qual nó será adicionado ao caminho. Devemos selecionar o nó não visitado com a distância mais curta (atualmente conhecida) até o nó de origem.

A partir da lista de distâncias, podemos detectar imediatamente que este é um nó 2 cuja distância é 6:

Adicionamos ao caminho graficamente com uma borda vermelha ao redor do nó e uma aresta vermelha:

Também o marcamos como visitado adicionando um pequeno quadrado vermelho na lista de distâncias e riscando-o da lista de nós não visitados:

Agora precisamos repetir o processo para encontrar o caminho mais curto do nó de origem até o novo nó adjacente, que é o nó 3.

Você pode ver que temos dois caminhos possíveis 0 -> 1 -> 3 ou 0 -> 2 -> 3. Vamos ver como podemos decidir qual é o caminho mais curto.

O nó 3 já possui uma distância na lista que foi registrada anteriormente (7, veja a lista abaixo). Essa distância foi resultado de um passo anterior, onde somamos os pesos 5 e 2 das duas arestas que precisávamos cruzar para seguir o caminho 0 -> 1 -> 3.

Mas agora temos outra alternativa. Se escolhermos seguir o caminho0 -> 2 -> 3, precisaríamos seguir duas arestas 0 -> 2 e 2 -> 3 com pesos 6 e 8, respectivamente, o que representa uma distância total igual a 14.

Claramente, a primeira distância (existente) é menor (7 x 14), então escolheremos manter o caminho original 0 -> 1 -> 3. Só atualizamos a distância se o novo caminho for mais curto.

Portanto, adicionamos este nó ao caminho usando a primeira alternativa: 0 -> 1 -> 3.

Marcamos este nó como visitado e o riscamos da lista de nós não visitados:

Agora, repetimos esse processo.

Precisamos verificar os novos nós adjacentes que não visitamos até agora. Desta vez, esses nós são os nós 4 e 5, já que ambos são adjacentes ao nó 3.

Atualizamos as distâncias desses nós até o nó de origem, sempre tentando encontrar um caminho mais curto, se possível:

• No caso do nó 4: a distância é 17 para o caminho  0 -> 1 -> 3 -> 4.
• No caso do nó 5: a distância é 22 para o caminho 0 -> 1 -> 3 -> 5.

💡 Dica: Observe que só podemos considerar estender o caminho mais curto (marcado em vermelho). Não podemos considerar caminhos que nos levarão através de arestas que não foram adicionadas ao caminho mais curto (por exemplo, não podemos formar um caminho que passe pela aresta2 -> 3).

Precisamos escolher qual nó não visitado será marcado como visitado. Neste caso, é o nó 4 porque tem a distância mais curta na lista de distâncias. Adicionamos graficamente no diagrama:

Também o marcamos como "visitado" adicionando um pequeno quadrado vermelho na lista:

E o riscamos da lista de nós não visitados:

E repetimos o processo novamente. Verificamos os nós adjacentes: nós 5 e 6. Precisamos analisar cada caminho possível que podemos seguir para alcançá-los a partir de nós que já foram marcados como visitados e adicionados ao caminho.

No caso do nó 5:

• A primeira opção é seguir o caminho 0 -> 1 -> 3 -> 5, que tem uma distância de 22 para o nó de origem (2 + 5 + 15). Essa distância já foi registrada na lista de distâncias em uma etapa anterior.
• A segunda opção seria seguir o caminho 0 -> 1 -> 3 -> 4 -> 5, que tem uma distância de 23 para o nó de origem (2 + 5 + 10 + 6).

Claramente, o primeiro caminho é mais curto, então o escolhemos para nó 5.

No caso do nó 6:

• O caminho disponível é 0 -> 1 -> 3 -> 4 -> 6, que tem uma distância de 19 para o nó de origem (2 + 5 + 10 + 2).

Marcamos o nó com a distância mais curta (atualmente conhecida) como visitada. Neste caso, o nó6.

E o riscamos da lista de nós não visitados:

Agora temos este caminho (marcado em vermelho):

Apenas um nó ainda não foi visitado, o nó 5. Vamos ver como podemos incluí-lo no caminho.

Existem três caminhos diferentes que podemos seguir para alcançar o nó 5a partir dos nós que foram adicionados ao caminho:

• Opção 1: 0 -> 1 -> 3 -> 5 com uma distância de 22 (2 + 5 + 15).
• Opção 2: 0 -> 1 -> 3 -> 4 -> 5 com uma distância de 23 (2 + 5 + 10 + 6).
• Opção 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 com uma distância de 25 (2 + 5 + 10 + 2 + 6).

Selecionamos o caminho: 0 -> 1 -> 3 -> 5 com uma distância de 22.

Marcamos o nó como visitado e o riscamos da lista de nós não visitados:

E aí está! Temos o resultado final com o caminho mais curto do nó 0 até cada nó do grafo.

No diagrama, as linhas vermelhas marcam as arestas que pertencem ao caminho mais curto. Você precisa seguir essas arestas para seguir o caminho mais curto para chegar a um determinado nó no grafo a partir do nó 0.

Por exemplo, se você deseja alcançar o nó 6 a partir do nó 0, basta seguir as arestas vermelhas e estará, automaticamente, seguindo o caminho mais curto 0 -> 1 -> 3 -> 4 - > 6.

🔸 Resumindo

• Os grafos são usados para modelar conexões entre objetos, pessoas ou entidades. Eles têm dois elementos principais: nós e arestas. Os nós representam objetos e as arestas representam as conexões entre esses objetos.
• O algoritmo de Dijkstra encontra o caminho mais curto entre um determinado nó (que é chamado de "nó de origem") e todos os outros nós em um grafo.
• Este algoritmo usa os pesos das arestas para encontrar o caminho que minimiza a distância total (peso) entre o nó de origem e todos os outros nós.

Eu realmente espero que você tenha gostado do artigo e o tenha achado útil. Agora, você sabe como o algoritmo de Dijkstra funciona nos bastidores. Siga a autora no Twitter (@EstefaniaCassN) e confira os cursos da autora on-line.

Algoritmos de força bruta são exatamente o que parecem – métodos diretos de resolver um problema que dependem de poder computacional puro e de tentar todas as possibilidades em vez de técnicas avançadas para melhorar a eficiência.

Por exemplo, imagine que você tem um pequeno cadeado com uma combinação 4 números, cada um deles indo de 0 a 9. Você esquece sua combinação, mas você não quer comprar outro cadeado. Como você não consegue se lembrar de nenhum dos números, precisa usar um método de força bruta para abrir a fechadura.

Você, então, insere todos os números no cadeado a partir do zero e os experimenta um a um: 0001, 0002, 0003 e assim sucessivamente até que ele abra. Na pior das hipóteses, seriam necessárias 10⁴, ou 10 mil tentativas para encontrar sua combinação.

Um exemplo clássico em ciência da computação é o problema do caixeiro viajante (TSP). Suponha que um vendedor precisa visitar 10 cidades em todo o país. Como determinar a ordem em que essas cidades devem ser visitadas de modo que a distância total percorrida seja minimizada?

A solução da força bruta é simplesmente calcular a distância total para toda possibilidade de rota possível e, depois, selecionar a mais curta. Isso não é particularmente eficiente, pois é possível eliminar muitas rotas através algoritmos inteligentes.

A complexidade de tempo da força bruta é O(mn), que às vezes é escrito como O(n*m) . Então, se fôssemos procurar uma string de "n" caracteres em uma string de "m" caracteres usando força bruta, faríamos n * m tentativas.

Mais informações sobre algoritmos

Na ciência da computação, um algoritmo é simplesmente um conjunto de procedimentos passo a passo para solucionar um dado problema. Algoritmos podem ser projetados para realizar cálculos, processar dados ou realizar tarefas automatizadas de raciocínio.

Veja como a Wikipédia os define:

Um algoritmo é um método eficaz que pode ser expresso em uma quantidade finita de espaço e tempo e em uma linguagem formal bem definida para calcular uma função. Partindo de um estado e de uma entrada (talvez vazia) iniciais, as instruções descrevem uma computação que, quando executada, prossegue através de um número finito de estados sucessivos bem definidos, eventualmente produzindo uma "saída" e terminando em um estado final. A transição de um estado para o seguinte não é necessariamente determinista; alguns algoritmos, conhecidos como algoritmos aleatórios, incorporam entradas aleatórias.

Existem certos requisitos que um algoritmo deve cumprir:

1. Definitividade: cada etapa do processo é declarada com precisão.
2. Computabilidade efetiva: cada etapa do processo pode ser realizada por um computador.
3. Finitude: o programa terminará eventualmente com sucesso.

Alguns tipos comuns de algoritmos incluem:

• algoritmos de classificação
• algoritmos de pesquisa
• algoritmos de compressão.

As classes de algoritmos incluem:

• de grafos
• de programação dinâmica
• de ordenação
• de busca
• de cordas (strings)
• matemáticos
• de geometria computacional
• de otimização
• diversas

Embora tecnicamente não sejam uma classe de algoritmos, as estruturas de dados são frequentemente agrupadas com eles.

Eficiência

Os algoritmos são mais comumente julgados por sua eficiência e pela quantidade de recursos de computação necessários para concluir sua tarefa.

Uma maneira comum de avaliar um algoritmo é observar sua complexidade de tempo. Isso mostra como o tempo de execução do algoritmo aumenta à medida que o tamanho da entrada aumenta. Como os algoritmos de hoje precisam operar em grandes entradas de dados, é essencial que nossos algoritmos tenham um tempo de execução razoavelmente rápido.

Algoritmos de ordenação

Os algoritmos de ordenação são de vários tipos, dependendo de sua necessidade. Alguns, muito comuns e amplamente utilizados, são:

Quicksort (Ordenação rápida)

Não há discussão sobre ordenação que possa terminar sem a ordenação rápida. Aqui está o conceito básico (em inglês): Quick Sort

Mergesort

Um algoritmo de ordenação que se baseia no conceito de como os arrays ordenados são mesclados para gerar um array ordenado. Leia mais sobre isso aqui (em inglês): Mergesort

O currículo do freeCodeCamp enfatiza fortemente a criação de algoritmos. Isso ocorre porque aprender algoritmos é uma boa maneira de praticar suas habilidades em programação. Os entrevistadores geralmente testam os candidatos quanto aos algoritmos durante as entrevistas de emprego para desenvolvedores.

Livros sobre algoritmos em JavaScript (em inglês):

Data Structures in JavaScript

• Livro gratuito que cobre as estruturas de dados em JavaScript
• GitBook

Learning JavaScript Data Structures and Algorithms - Second Edition

• Trata de programação orientada a objetos, herança prototípica, algoritmos de ordenação e busca, quicksort, mergesort, árvores binárias de busca e conceitos avançados de algoritmos
• Amazon
• ISBN-13: 978-1785285493

Data Structures and Algorithms with JavaScript: Bringing classic computing approaches to the Web

• Trata de recursão, algoritmos de ordenação e busca, listas vinculadas e árvores binárias de busca.
• Amazon
• ISBN-13: 978-1449364939