Algoritmos de Ordenação em C #2

 

Neste artigo, discutiremos sobre os algoritmos sofisticados de ordenação em arrays. Começaremos por um breve resumo sobre a técnica de dividir para conquistar que será de importante uso para as implementações. Em seguida, podemos dar início a uma breve introdução sobre os algoritmos de merge sort, quicksort e heapsort.

 

A técnica que mudou a programação: dividir para conquistar!

A Divisão e Conquista ou, do inglês, Divide and Conquer, é uma técnica de projeto e análise de algoritmos muito utilizada na computação. Ela se baseia em dividir recursivamente um problema em subproblemas cada vez menores, até que o problema como um todo possa ser solucionado. O caso-base, quando aplicamos essa técnica em um array, geralmente será um array vazio ou com apenas um elemento.

O foco deste artigo não é explicar sobre recursão, espera-se do leitor que ele já tenha domínio e compreensão sobre esse tema.

Um problema clássico que pode ser resolvido utiliando essa técnica é a Torre de Hanoi. A técnica soluciona o problema através de três passos:

• Divisão: o problema maior é dividido em subproblemas menores.

• Conquista: se o subproblema for pequeno suficiente, então, resolva-o diretamente, caso contrário, resolva cada subproblema recursivamente.

• Combinação: o resultado dos problemas menores são combinados até que seja obtida a solução do problema maior.

Esses são os três passos universais da técnica de divisão e conquista. A seguir, aplicaremos eles na prática.

 

Algoritmos sofisticados de ordenação

Merge Sort

O algoritmo de merge sort é um dos algoritmos populares que utiliza a técnica de dividir para conquistar. O funcionamento desse algoritmo é o seguinte: ele divide recursivamente o array em duas partes, também chamadas de subarrays, até que cada posição dele seja considerada um array de um único elemento. Em seguida, o algoritmo combina dois arrays para obter um array maior e ordenado. Esse processo se repete até que exista apenas um array e que ele esteja totalmente ordenado.

A combinação dos arrays é feita intercalando seus elementos conforme o sentido da ordenação (crescente ou decrescente).

Uma possível implementação é a seguinte:

O merge sort utiliza duas funções em sua implementação de divisão e conquista: uma função para dividir os arrays em subarrays cada vez menores, mergeSort, e outra função para intercalar os dados de forma ordenada em um array meior, merge. O princípio desse algoritmo é dividir o array ao meio se ele tiver mais do que um elemento, esse processo é recursivo, ou seja, dividiremos ele ao meio até chegar ao caso-base — um array de um único elemento. A função mergeSort se encarrega dessa divisão ao meio.

Ao chegar no caso-base, a recursão termina, e inicia-se o processo de intercalação do array pela função merge. A ideia da função merge é bastante simples: ela recebe as duas metades do array, neste caso, inicio e meio + 1 e as combina em um array auxiliar temp. Em seguida, a função percorre o array temp verificando, a cada passo, qual array tem o menor elemento. O menor elemento é inserido em temp e o algoritmo incrementa o contador do array escolhido.

Caso um dos arrays tenha chegado ao final, o algoritmo irá copiar o restante do array que sobrou para o final de temp na próxima iteração.

Por fim, o algoritmo copia os dados do array temp para o array original.

A figura abaixo ilustra o processo de ordenação completa de um array utilizando o algoritmo de merge sort:

 

Quicksort

O algoritmo de quicksort, assim como o algoritmo de merge sort, faz parte da categoria de algoritmos sofisticados de ordenação. É um algoritmo muito utilizado na prática do desenvolvimento de software e, além disso, utiliza a estratégia de dividir para conquistar.

Vale lembrar que, dado um determinado array, não há necessidade de ordena-lo caso o array for vazio ou possua apenas um elemento.

A biblioteca-padrão da linguagem C possui uma função chamada qsort, que nada mais é do que uma implementação do quicksort.

O quicksort segue uma lógica: primeiro, escolha um elemento do array. Esse elemento é chamado de pivô. Em seguida, encontre os elementos que são menores que o pivô e também os elementos que são maiores. Essa lógica é chamada de particionamento. A ideia do particionamento é, no fim, obter um subarray contendo todos os valores menores do que o pivô, o pivô, e um subarray contendo todos os valores maiores do que o pivô.

Não necessariamente os subarrays precisam estar ordenados, eles serão apenas particionados.

O algoritmo segue os seguintes passos:

• Passo 1: escolha um pivô.
• Passo 2: particione o array em dois subarrays, separando-os entre elementos menores do que o pivô (rearranjados à esquerda) e elementos maiores do que o pivô (rearranjados à direita).
• Passo 3: execute o quicksort recursivamente em ambos subarrays. O processo se repete até que cada partição tenha apenas um elemento.

A escolha de um bom pivô faz toda diferença no algoritmo. A eficácia do quicksort está ligada à eficiência da sua funcão particiona que separa os dados e calcula o pivô.

Uma possível implementação é a seguinte:

A função particiona recebe um array e as posições de inicio e fim. Em seguida, será definida as variáveis de esq e dir, indicando, respectivamente, as posições mais a esquerda (inicio) e mais a direita (fim) da partição, sendo o primeiro valor da partição escolhido como pivô. O restante do processo é ilustrado pelas figuras abaixo:

Primeira etapa do algoritmo: particionar o array:

Segunda etapa do algoritmo: aplicar o algoritmo de quicksort para ordenação dos subarrays:

 

Heapsort

O algoritmo de heapsort é mais um algoritmo sofisticado de ordenação. A ideia básica deste algoritmo é transformar o array de dados em uma estrutura do tipo heap, isto é, uma árvore binária completa.

Uma árvore binária completa é uma estrutura onde todos os nós possuem dois filhos, com excessão dos nós folhas.

Uma implementação eficiente para a heap é representá-la na forma de um array. Assim, o array começa com o elemento da raiz e seus filhos se encontram nas posições subsequentes, a mesma lógica vale para os filhos desses filhos.

A estrutura de heap permite a recuperação e remoção do elemento de maior valor do array. Além disso, cada posição i do array passa a ser considerada o pai de duas outras posições, chamadas filhos. Para encontrar cada filho, em relação ao pai, será utilizado o seguinte cálculo de indíces: 2i (filho à esquerda) e 2i + 1 (filho à direita). Em seguida, o algoritmo reorganiza o array para que o pai seja sempre maior que os dois filhos. Por fim, o maior elemento do array será também o pai dos demais elementos. Este elemento poderá ser removido da heap e adicionado na última posição do array. O processo se repete para toda heap.

Uma possível implementação para este algoritmo é a seguinte:

criaHeap: responsável pela criação da heap a partir de certo elemento do array.

heapSort: responsável por criar a heap e ordenar os dados.

A função criaHeap armazena a posição do pai em uma variável auxiliar (aux) e em seguida calcula e verifica a existência dos filhos. Caso só exista um filho, apenas ele será considerado o maior naquele nível. Caso exista dois filhos, será necessário selecionar o maior deles. Tendo selecionado o maior filho, o próximo passo é verificar se aux é menor que ele. Se a afirmação for verdadeira, a posição do pai receberá o valor do maior filho. Logo, o filho será considerado o novo pai, que também terá o seu filho calculado para a continuação do processo de ordenação.

Caso a afirmação da linha 12 do código seja falsa, o filho recebe o valor de uma posição além do final do array fim para encerrar o comando while. Por fim, ao encerrar o laço, o valor aux é copiado para a posição do pai atual.

As figuras abaixo ilustram esse processo:

Primeira etapa do algoritmo: chamada da função criaHeap e criação da heap:

O objetivo da função criaHeap é fazer com que toda posição pai analisada seja sempre maior que seus filhos. Contudo, fazer com que toda posição pai seja sempre maior que seus filhos não significam que determinada posição pai será maior que os filhos de seus filhos.

Segunda etapa do algoritmo: a função heapSort realiza a remoção do maior elemento e a reconstrução da heap:

 

Análise de complexidade

Considerando um array com n elementos, o tempo de execução de cada algoritmo é:

Algoritmo	Melhor caso	Caso médio	Pior caso
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quicksort	O(n log n)	O(n log n)	O(n^2)
Heapsort	O(n log n)	O(n log n)	O(n log n)

 

Conclusão

A utilização de bons algoritmos de ordenação nas aplicações podem fazer total diferença no resultado final. Este artigo, junto com o anterior, abordou de forma direta os principais algoritmos, sofisticados e básicos, de ordenação interna e suas respectivas vantagens em relação ao tempo de complexidade de cada um.

 

Referências

Estrutura de Dados Descomplicada - Em Linguagem C , por André Backes

Entendendo Algoritmos, por Aditya Bhargava

Programação Java: algoritmo de divisão e conquista

Algorithms - Merge Sort

O Algoritmo Heapsort

Obrigado pela leitura!