Estruturas de Dados e Algoritmos: Merge Sort, Quicksort, Busca Binária e Mais

Merge Sort

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar. Sua ideia básica consiste em:

• Dividir: o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade.
• Conquistar: após todos os sub-problemas terem sido resolvidos, ocorre a conquista, que é a união das resoluções dos sub-problemas.

Como o algoritmo do Merge Sort usa a recursividade em alguns problemas, esta técnica pode não ser muito eficiente devido ao alto consumo de memória e tempo de execução.

Quicksort

O Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. Os passos são:

1. Escolha um elemento da lista, denominado pivô.
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição.
3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores.

Busca Binária

(em inglês binary search algorithm ou binary chop) é um 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. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor.

Busca Sequencial

É o tipo de busca mais simples. Não requer ordenação dos elementos. Pesquisa sequencialmente do primeiro até o último registro.

Hashing

Transformações de Chave, ou Tabela Hash, ou Tabelas de Dispersão. "Hashing" significa fazer picadinho ou fazer uma bagunça. É uma técnica que objetiva organizar um conjunto de dados, caracterizados por uma chave, de forma que o acesso tenha o menor custo possível. Em estruturas tradicionais, se os registros forem mantidos ordenados, algoritmos eficientes podem garantir busca a um custo.

Tabelas Hash

Se bem projetadas, podem garantir buscas a um custo constante O(1). Os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de pesquisa. O preço pago por esta eficiência será o uso maior de memória. É uma estrutura de dados especial que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. É algumas vezes traduzida como tabela de escrutínio.

Heap

É uma estrutura de dados organizada como árvore binária balanceada, seguindo algumas regras. Este pode ser implementado em um arranjo, para que ele seja acessado como uma árvore binária. Se estiver bem implementado, estas são macros ou procedimentos "inline". Estas operações podem ser executadas rapidamente usando operações bit a bit. Para o filho esquerdo, desloca os bits à esquerda; para o direito, desloca os bits para a esquerda e aplica a operação "ou" com 1. Para encontrar o pai, desloca um bit à direita. A vantagem de usar operações bit a bit é que cada uma delas usa apenas um clock do processador, sendo altamente eficiente.

Utilizações do Heap

É no algoritmo de ordenação heapsort, que utiliza a propriedade do heap de o maior (ou menor valor) localizar-se na raiz do mesmo e fazer a ordenação dos dados de uma maneira bastante eficiente. Também pode ser usada como heaps de prioridades, onde a raiz é a maior prioridade. Com relação ao vetor a, inserção e remoção são da ordem O(log(n)). Outra utilização de heaps são em algoritmos de seleção.

Inserir na Heap

Podemos simplesmente adicioná-lo no final do array e depois empurrá-lo para cima na árvore enquanto ele for menor que o pai (ou maior, se for um heap de máximo). Já o corrigeDescendo realiza o mesmo processo, mas é utilizado quando o elemento precisa ser empurrado para baixo, e não para cima. Isso acontece na remoção, pois nesta operação selecionamos o último elemento do array e trocamos com a raiz. Assim, podemos descartar a raiz (que está no final do array agora, bastando remover o último elemento do array). Porém, o último elemento do array (que foi movido para a raiz) provavelmente não é o menor, e a raiz deve sempre guardar o menor elemento. Portanto, devemos empurrar o elemento para baixo até que o heap esteja corrigido.

Heapsort

É um algoritmo de ordenação generalista e faz parte da família de algoritmos de ordenação por seleção. O heapsort utiliza uma estrutura de dados chamada heap, para ordenar os elementos à medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada, lembrando-se sempre de manter a propriedade de max-heap.

A heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais) ou como um vetor. Para uma ordenação decrescente, deve ser construída uma heap mínima (o menor elemento fica na raiz). Para uma ordenação crescente, deve ser construída uma heap máxima (o maior elemento fica na raiz).

Recursão

É um método de programação no qual uma função pode chamar a si mesma. O termo é usado de maneira mais geral para descrever o processo de repetição de um objeto de um jeito similar ao que já fora mostrado. Muitos problemas em computação têm a propriedade de que cada instância sua contém uma instância menor do mesmo problema.

Fibonacci

Essa sequência tem uma lei de formação simples: cada elemento, a partir do terceiro, é obtido somando-se os dois anteriores. Veja: 1+1=2, 2+1=3, 3+2=5 e assim por diante.

Inserção na ABB

Uma inserção em uma árvore binária de busca deve respeitar a propriedade fundamental dessa estrutura, mantendo menores à esquerda e maiores à direita. Para que isso seja possível, é interessante que a interface de programação da nossa árvore ofereça um método que faça a inserção de um elemento garantindo tal propriedade.

O algoritmo para a inserção funciona de forma semelhante à busca. Vamos descendo na árvore com o objetivo de encontrar o local certo onde o elemento deve ser inserido, verificando sempre se devemos continuar o percurso na subárvore à esquerda ou à direita do nó. Diferentemente da busca, na inserção nossa travessia termina ao encontrarmos um nó folha, no qual o elemento a ser inserido é adicionado como filho — à esquerda, se o elemento a ser adicionado for menor que o nó, ou à direita, caso contrário.

Remoção na ABB

Casos a serem considerados no algoritmo de remoção de nós de uma ABB:

• Caso 1: o nó é folha. O nó pode ser retirado sem problema.
• Caso 2: o nó possui uma sub-árvore (esq./dir.). O nó-raiz da sub-árvore (esq./dir.) pode substituir o nó eliminado.
• Caso 3: o nó possui duas sub-árvores. O nó cuja chave seja a menor da sub-árvore direita pode substituir o nó eliminado; ou, alternativamente, o de maior valor da sub-árvore esquerda pode substituí-lo.

O método _min retorna o nó que contém o menor elemento em uma subárvore, isto é, o elemento mais à esquerda na subárvore em questão.