Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
O algoritmo de Linear Search percorre o array elemento por elemento até encontrar o valor procurado.
- Tempo: O(n)
- Espaço: O(1)
Devemos percorrer cada elemento do array e compará-lo com o valor procurado. Quando o valor é encontrado, retornamos seu índice ou seu valor, dependendo da implementação.
O algoritmo de Binary Search consiste em dividir o array ao meio e verificar se o valor procurado é menor ou maior do que o valor que se encontra na metade do array. Para isso é necessário que o array esteja previamente ordenado. Se o valor procurado for exatamente igual ao elemento do meio, ele foi encontrado e retornado. Se o valor for maior, descartamos a metade esquerda do array e iniciamos pela parte direita, dividindo novamente ao meio e refazendo a busca. Se o valor for menor, descartamos a metade direita e seguimos a mesma lógica no array esquerdo, até que o elemento da metade seja o valor procurado.
- Tempo: O(log n)
- Espaço: O(1)
Devemos ter três variáveis de referência: uma para armazenar o último índice, uma para armazenar o primeiro índice, iniciando como 0, e outra para armazenar o índice do meio, calculado a partir dos índices inicial e final da busca.
Verificamos sempre se ainda há elementos a serem analisados, pois pode ocorrer de o valor não existir no array. Dessa forma, encerramos o loop quando o índice inicial ultrapassar o índice final.
Verificamos se o valor do meio é igual ao valor que procuramos. Caso verdadeiro, retornamos esse valor.
Se o valor que procuramos for menor que o valor encontrado no meio, então definimos a variável end como o índice da metade menos 1. Dessa forma iniciamos a busca apenas na metade esquerda e repartimos novamente ao meio. Se o valor for maior, atribuímos o índice da metade mais 1 para a variável start e começamos a busca apenas na metade direita, repartindo novamente ao meio até encontrarmos o valor procurado.
A recursão consiste em uma função que chama ela mesma até chegar no caso base definido no algoritmo A recursão consiste em uma função chamando ela mesma até que uma condição de parada seja atingida. Cada chamada é adicionada à pilha de execução (Call Stack) e, quando o caso base é alcançado, as chamadas começam a retornar uma por uma.
function exemplo() {
if(casoBase)
return;
return exemplo();
}Sempre que uma função chama ela mesma devemos pensar em duas partes:
- O caso base, que é responsável por encerrar a recursão.
- O passo recursivo, que aproxima o problema do caso base.
Se não existir um caso base, a função continuará chamando a si mesma infinitamente.
O algoritmo de Bubble Sort funciona verificando se o elemento atual é maior que o próximo elemento do array. Se for, é feita uma troca dos valores entre as duas posições: o valor atual fica no lugar do próximo e vice-versa. Se o valor atual não for maior que o próximo valor do array, então essa comparação já se encontra ordenada.
A cada troca realizada, o contador de trocas é incrementado. Sempre que uma rodada é finalizada, o último elemento do array já se encontra ordenado na posição correta, então não é necessário percorrê-lo novamente. Dessa forma definimos a quantidade de rodadas e iteramos apenas até onde ainda não foi ordenado. Se uma rodada foi concluída, o último elemento já está ordenado corretamente, então na próxima percorremos apenas até o tamanho do array menos a quantidade de rodadas.
Em cada rodada verificamos se houve trocas. Se finalizarmos uma rodada sem nenhuma troca, é porque naturalmente o array já está ordenado, então encerramos o loop.
- Tempo: O(n²)
- Espaço: O(1)
Neste raciocínio declaramos duas variáveis: uma contadora de trocas de posições e outra de rodadas concluídas.
O contador de trocas define se houve troca de posições. A cada início de rodada ele é definido como 0.
O contador de rodadas é incrementado a cada rodada concluída. Dessa forma conseguimos reduzir a quantidade de iterações no array, pois sempre verificamos até o último índice do array menos a quantidade de rodadas. Em cada rodada o último elemento iterado estará ordenado corretamente.
Se finalizarmos o loop sem fazer nenhuma troca de posições, isso significa que todo o array já está ordenado e o loop é encerrado.
Verificamos a cada iteração se o valor do índice atual é maior que o valor do próximo índice. Caso verdadeiro, salvamos o valor do índice atual em uma variável auxiliar, atribuímos ao índice atual o valor do próximo índice e, por fim, atribuímos ao próximo índice o valor armazenado na variável auxiliar.
O algoritmo de Selection Sort utiliza uma estratégia diferente do Bubble Sort. Ele seleciona o menor valor a cada iteração. É verificado através de dois loops o valor atual e os valores seguintes. Inicialmente assumimos que o valor atual é o menor encontrado. Se algum dos próximos valores for menor que ele, então esse novo valor passa a ser considerado o menor.
Ao final da busca, se o índice do menor valor for diferente do índice atual, realizamos a troca. O valor atual vai para o índice do menor valor e o menor valor vai para o índice atual, ordenando corretamente o array sempre do primeiro elemento em diante.
- Tempo: O(n²)
- Espaço: O(1)
Neste raciocínio definimos dois laços de repetição: um para iterar cada elemento do array e outro para comparar o valor do índice atual com cada valor do array que vem depois dele.
Definimos uma variável inicial no primeiro loop que representa o índice do menor valor, começando com o índice atual, pois inicialmente assumimos que ele é o menor valor encontrado.
Definimos um laço aninhado e nele verificamos se o próximo número é menor que o valor localizado no índice armazenado nessa variável. Caso verdadeiro, essa variável recebe o índice desse novo menor valor.
Ao final de cada iteração desse laço aninhado, verificamos se o índice atual é diferente do índice armazenado na variável do menor valor. Caso verdadeiro, isso significa que o valor do índice atual é maior que o valor localizado no índice armazenado nessa variável. Então realizamos a troca de posições salvando o valor do índice atual em uma variável auxiliar, atribuímos ao índice atual o valor localizado no índice do menor valor e, por fim, salvamos no índice onde estava o menor valor o valor armazenado na variável auxiliar.
O algoritmo Merge Sort funciona com a ideia de "Dividir para conquistar". Basicamente a ideia é dividir o array recebido no meio, etapa por etapa até que sobre apenas um valor dentro de cada array resultante da divisão. Um array de 6 elementos não ordenados, ao final das chamadas recursivas, será dividido até que cada subarray contenha apenas um elemento. A partir desse ponto, começamos a unir os subarrays, comparando seus elementos e formando novos subarrays ordenados, até reconstruir completamente o array em ordem.
- Tempo: O(n log n)
- Espaço: O(n)
O algoritmo necessita de duas funções. Uma para separar o array até sobrar 1 elemento e a outra função para unir os elementos até que se torne o array ordenado.
- Unir
Primeiro devemos declarar a função que une os arrays, nela iremos receber dois arrays como parâmetros, um da esquerda e outro da direita e teremos uma variável que armazenará o novo array ordenado e duas variáveis para controlar os índices dos arrays da esquerda e da direita.
Iremos percorrer cada elemento enquanto os índices forem menores que os seus tamanhos, e verificar se o elemento da esquerda é menor que o elemento da direita, caso verdadeiro, adicionamos o valor da esquerda no array ordenado e incrementamos no índice do lado esquerdo, caso falso adicionamos o elemento do array da direita no array ordenado e incrementamos o índice do lado direito, até que um dos arrays termine.
Ao final do while um dos arrays terá sido totalmente percorrido. Então basta concatenar ao array ordenado os elementos restantes do outro array.
- Separar
Recebemos o array não ordenado como parâmetro e definimos um caso base se o tamanho do array for menor ou igual a 1. Neste caso por definição o array já está ordenado.
definimos o índice do meio do array arredondando o valor para baixo, para evitar que ao dividir arrays com tamanhos ímpares, recebamos um número flutuante.
definimos o array da esquerda e o array da direita
e retornamos a função merge e passando recursivamente como argumento a função de separar, com o argumento sendo o array da esquerda e o outro o array da direita.
Obs: Durante a divisão o array ainda não é ordenado. A ordenação acontece apenas durante a etapa de união (merge).
O algoritmo funciona definindo um valor pivô que irá ser usado para compararar todos os outros valores, este valor pivô pode ser qualquer elemento do array, a escolha do elemento pivô impacta diretamente a perfomance. Iremos comparar de forma recursiva, se os valores do array em cada posição é menor ou maior que o valor definido como pivô. Os menores vão para um subarray referente os da esquerda e os maiores para um subarray referente aos da direita. E iremos chamar a função passando os valores e definindo esses parâmetros, até que entre no caso base, que é o array ter 1 ou menos elementos, pois assim estará ordenado. O valor pivô fica sempre logo depois do array da esquerda terminar.
- Tempo: O(n log n)
- Espaço: O(n)
Definimos imediatamente um caso base, pois é uma função recursiva e iremos retornar quando o array passado como argumento tiver 1 elemento ou menos, pois por definição, estará ordenado.