Note Pesquisa em vetores ou listas de modo sequencial, elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente.

Características

• Algoritmo simples
• Menos otimizado
• Não recomendado para manipulação de um grande volume de dados

Exemplo:

arr[] = {0,4,6,7,8,32}
elemento da busca: 8

• 1º iteração:

  arr[] = {0,4,6,7,8,32}
  0 == 8? Não, passa para o próximo elemento.

• 2º iteração:

  arr[] = {0,4,6,7,8,32}
  4 == 8? Não, passa para o próximo elemento.

• 3º iteração:

  arr[] = {0,4,6,7,8,32}
  6 == 8? Não, passa para o próximo elemento.

• 4º iteração:

  arr[] = {0,4,6,7,8,32}
  7 == 8? Não, passa para o próximo elemento.

• 5º iteração:

  arr[] = {0,4,6,7,8,32}
  8 == 8? Sim, interrompe a iteração e retorna o elemento.

Note Algoritmo de busca em vetores que segue o paradigma de Divisão e Conquista. Ela parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso.

low = 0
high = número de elementos
mid = (low + high) / 2

Os referênciais operam com íncices, logo, se há o array = {1,2,3,4,5} e low = 0, low é igual ao índice 0 que contém o elemento de valor 1.

Características

• Algoritmo mais sofisticado
• Melhor caso O(1)
• Mais eficiente
• Requer estruturas ordenadas

Exemplo:

arr[] = {0,4,6,7,8,32}
elemento da busca: 8
mid = (0 + 5) / 2 = 2

• 1º iteração:

  low -> elemento 0
  high -> elemento 32
  mid = -> elemento 6

  8 < mid? Se sim, high atualiza para (mid - 1).
  8 > mid? Se sim, low atualiza para (mid + 1).

  Em nosso exemplo, 8 é maior que a referência mid, então a referência low é atualizada. Consequentemente, como delimitamos a área de busca com essa ação, a referência de mid também é atualizada.

Atualizações:
estrutura arr[] = {7,8,32}
low = elemento 7
high = elemento 32
mid = (0 + 2) / 2 = 1 -> elemento 8

• 2º iteração:

  low -> elemento 7
  high -> elemento 32
  mid -> elemento 8

  8 < mid? Se sim, high atualiza para (mid - 1).
  8 > mid? Se sim, low atualiza para (mid + 1).

  Como não é nenhum dos casos, é identificado que mid == elemento da busca, então mid é retornado e a pesquisa encerrada!

Note O algoritmo funciona sempre buscando o maior elemento, em um par usado para comparação, para o mover para direita. E após isso, fazer o mesmo com o segundo maior elemento, depois com o terceiro... continuamente, até ordenar todos elementos (ordem crescente).

Características:

• Compara elementos adjacentes (dois a dois)
• Não recomendado para manipulação de um grande volume de dados
• Algoritmo estável
• Não requer nenhum espaço de memória adicional

Exemplo:

arr[] = {2,1,3,5,4}

• 1º iteração: 2 > 1? Sim, os mesmos são invertidos, arr[] = {1,2,3,5,4}

• 2º iteração: 2 > 3? Não, estado do array é mantido e o próximo elemento se torna o comparador

• 3º iteração: 3 > 5? Não, estado do array é mantido e o próximo elemento se torna o comparador

• 4º iteração: 5 > 4? Sim, os mesmos são invertidos, arr[] = {1,2,3,4,5}

Como não há mais elementos para realizar comparação, é compreendido que o array se encontra completamente ordenado.

Note Funciona dividindo uma matriz em submatrizes menores, classificando cada submatriz e, em seguida, mesclando as submatrizes classificadas novamente para formar a matriz classificada final.

Características:

• Desempenho garantido no pior caso (limite superior igual ao limite inferior)
• Algoritmo estável
• Algoritmo recursivo
• Gasto extra de memória

Exemplo:

[12,31,25,8,32,17,40,42]

• 1º iteração: primeiro divida a matriz dada em duas metades, conforme mid = número de elementos / 2, ou seja, mid = 8 / 2 = 4.

  [12,31,25,8] [32,17,40,42]

• 2º iteração: novamente divida essas duas matrizes em metades. Como eles são de tamanho 4, então divida-os em novas matrizes de tamanho 2.

  [12,31] [25,8] [32,17] [40,42]

• 3º iteração: agora, novamente divida essas matrizes para obter o valor atômico que não pode ser mais dividido.

  [12] [31] [25] [8] [32] [17] [40] [42]
  
  

Agora, combine-os da mesma maneira que foram quebrados. Na combinação, primeiro compare o elemento de cada matriz e, em seguida, combine-os em outra matriz em ordem classificada.

• 4º iteração:

  [12,31] [25] [8] [32] [17] [40] [42]

• 5º iteração:

  [12,31] [8,25] [32] [17] [40] [42]

• 6º iteração:

  [12,31] [8,25] [17,32] [40] [42]

• 7º iteração:

  [12,31] [8,25] [17,32] [40,42]

• 8º iteração: agora compare as matrizes com dois valores de dados e mescle-os em uma matriz de valores encontrados em ordem classificada.

  [8,12,25,31] [17,32,40,42]

• 9º iteração: por fim, há uma fusão final das matrizes.

  [8,12,17,25,31,32,40,42]

Note Classificação baseada no algoritmo Dividir e Conquistar que escolhe um elemento como um pivô e particiona a matriz dada em torno do pivô escolhido, colocando o pivô em sua posição correta na matriz classificada.

Características:

• Algoritmo instável (pior caso O(n²))
• Algoritmo recursivo
• Trabalha com referência (pivô)

A primeira etapa do Quick Sort é a partição. A partição é feita recursivamente em cada lado do pivô depois que o pivô é colocado em sua posição correta e isso finalmente classifica a matriz.

O pivô pode ser escolhido de diversos modos, mas aqui usaremos a lógica de definir o pivô sempre como o elemento do meio de uma matriz (pivô = número de elementos \ 2).

Exemplo:

[10,80,30,90,40,50,70]

pivô = 7 \ 2 = 3... lembrando que há posição 0, o elemento de valor 90 é o 3º elemento da matriz.

• 1º iteração: alocamos todos os elementos de valor menor que o do nosso pivô a esquerda e os maiores a direita.

  pivô
  [90]

  esquerda -> [10,80,30,40,50,70]

Agora, basta realizar o mesmo passo a passo com as submatrizes formadas, até não ser mais possível particionar.

• 2º iteração:

  [10,80,30,40,50,70]

  pivô
  [40]

• 3º iteração:

  [10,30]
  Como a submatriz possui apenas 2 elementos, qualquer um dos dois pode ser pivô.

  pivô
  [10]

  [30] <- direita

• 4º iteração:

  [80,50,70]

  pivô
  [50]

  [80,70] <- direita

• 5º iteração:

  [80,70]

  pivô
  [70]

  [80] <- direita

Agora que não é mais possível realizar partições, se for agrupado novamente os elementos conforme a ordem que os organizamos após as iterações, obteremos: [10,30,40,50,70,80,90]

Note Funciona de forma semelhante à maneira como você classifica as cartas de baralho em suas mãos. O array é virtualmente dividido em uma parte classificada e uma não classificada. Os valores da peça não classificada são selecionados e colocados na posição correta na parte classificada.

Características:

• In-place: Apenas requer uma quantidade constante de O(1) espaço de memória adicional
• Algoritmo estável
• Muitas trocas, e menos comparações

Exemplo:

arr[] = {12, 11, 13, 5, 6}

• 1º iteração: inicialmente, os dois primeiros elementos da matriz são comparados na classificação de inserção.

  {12,11,13,5,6}

  12 < 11 || 11 < 12? Os mesmos são invertidos, arr[] = {11,12,13,5,6}

• 2º iteração: agora, passe para os próximos dois elementos e compare-os

  {11,12,13,5,6}

  12 < 13 || 13 < 12? Estado do array é mantido e o próximo elemento se torna o comparador

• 3º iteração:

  {11,12,13,5,6}

  13 < 5 || 5 < 13? Os mesmos são invertidos, arr[] = {11,12,5,13,6}

  Após a troca, os elementos 12 e 5 não são classificados, portanto, trocam novamente.

  {11,12,5,13,6}

  arr[] = {11,5,12,13,6}

  Aqui, novamente 11 e 5 não são classificados, portanto, troque novamente.

  {11,5,12,13,6}

  arr[] = {5,11,12,13,6}

  Aqui, novamente 11 e 5 não são classificados, portanto, troque novamente.

  {11,5,12,13,6}

  arr[] = {5,11,12,13,6}

• 4º iteração:

  {5,11,12,13,6}

  13 < 6 || 6 < 13? Os mesmos são invertidos, arr[] = {5,11,12,6,13}

  Agora, 6 é menor que 12, portanto, troque novamente.

  {5,11,12,6,13}

  arr[] = {5,11,6,12,13}

  Aqui, também a troca faz 11 e 6 não classificados, portanto, troque novamente.

  {5,11,6,12,13}

  arr[] = {5,6,11,12,13}

Finalmente a estrutura está ordenada.