ordenacao_metodo_eficiente

Prévia do material em texto

Ordenação de dados — 
métodos eficientes
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Definir o método de ordenação Quicksort.
 � Identificar o método de ordenação Mergesort.
 � Descrever a comparação entre os métodos de ordenação simples e 
eficientes.
Introdução
Os métodos de ordenação são algoritmos muito utilizados quando é 
necessário que os dados de uma lista de valores, originalmente desorde-
nada, sejam recuperados de maneira ágil e facilitada. Entre os métodos 
de ordenação eficientes, alguns dos mais conhecidos são o Quicksort 
e o Mergesort, conhecidos por utilizarem a estratégia da divisão e con-
quista, na qual um problema deve ser dividido em vários problemas 
menores, que serão solucionados até que o problema maior possa ser 
completamente resolvido.
Neste capítulo, você estudará os métodos de ordenação Quicksort e 
Mergesort, além da comparação entre os métodos de ordenação simples 
e eficientes.
Método de ordenação Quicksort
O Quicksort é um algoritmo que consiste em um método de ordenação por 
comparação e troca, muito utilizado por ser rápido e eficiente. Esse algoritmo 
foi elaborado em 1960, por um estudante da Universidade de Moscovo, en-
quanto ele tentava traduzir um dicionário do idioma inglês para o idioma 
russo (HERBERT, 1996). 
A premissa básica do Quicksort é reduzir o problema inicial em diversos 
problemas menores, que possam ser resolvidos de forma fácil e rápida. O 
Quicksort é um dos algoritmos mais conhecidos, por utilizar uma estratégia 
de funcionamento chamada divisão e conquista.
Divisão e conquista, expressão do inglês divide and conquer, é uma estratégia de 
projeto algorítmico que envolve a divisão de um problema maior, recursivamente, em 
problemas menores, solucionando-os até que o problema todo possa ser resolvido. 
Você pode compreender, portanto, que o problema inicial será resolvido por meio 
da combinação dos resultados obtidos pela sua divisão em problemas menores. 
Muitos problemas computacionais podem ser resolvidos pela divisão e conquista, 
mas, certamente, sua principal utilização é na ordenação de elementos.
O método de ordenação Quicksort se baseia na ideia de partições. Em 
geral, o funcionamento do Quicksort envolve a seleção de um valor (pivô), 
após o vetor inicial passa a ser dividido em duas partições, separando todos 
os elementos maiores ou iguais ao pivô de um lado e os elementos menores 
do que o pivô de outro. Depois disso, esse processo de divisão é repetido para 
cada uma das partições restantes, até que o vetor esteja totalmente ordenado 
(DEITEL; DEITEL, 2011).
Essa explicação inicial pode ser melhor entendida, se considerarmos o 
exemplo de um vetor inicial com os elementos 0 9 5 3 6 4, e um pivô valendo 
5, conforme segue:
Esse processo de particionamento deverá ser repetido infinitamente, até que 
o vetor esteja ordenado por completo, ou seja, o processo forma naturalmente 
um algoritmo recursivo.
Ordenação de dados — métodos eficientes2
Na área da ciência da computação, a recursividade é a característica que uma função, 
um método ou uma sub-rotina possui de poder fazer a chamada, ou requisitar a si 
mesma. A recursividade é comum nos algoritmos baseados na estratégia de divisão 
e conquista, em que se divide um problema em problemas menores para poder 
resolvê-lo.
O pivô, que é o elemento do vetor que servirá de comparação com cada 
um dos demais elementos, pode ser escolhido de forma aleatória, mas uma 
das melhores maneiras de escolhê-lo é verificando o elemento mediano de 
toda a faixa de valores que compõem o vetor. Uma das formas mais comuns 
de escolher o pivô é defini-lo como uma das extremidades da lista de valores, 
ou o elemento mais à esquerda ou o mais à direita, e o comparando com cada 
um dos demais. 
Independentemente da forma escolhida para definir o pivô, o Quicksort 
é um método de ordenação de ótimo desempenho, principalmente porque é 
um dos algoritmos de divisão e conquista que faz o menor número médio de 
trocas entre os elementos da lista de valores.
Por outro lado, se a lista de valores for muito extensa, e o pivô escolhido 
para uma determinada iteração for exatamente o menor ou o maior valor de 
todos, o Quicksort vai efetuar todas as comparações entre todos os elementos 
e não fará nenhuma troca, o que provavelmente vai comprometer o rendi-
mento do algoritmo como um todo, pois isso pode acontecer várias vezes até 
a ordenação final.
Para exemplificar o método de ordenação Quicksort, pode-se criar um 
arquivo em C, que sirva para ordenar uma lista de valores com sete números. 
O código utilizado é o seguinte:
3Ordenação de dados — métodos eficientes
Ordenação de dados — métodos eficientes4
O código apresentado funciona da seguinte maneira: das linhas 1 a 3 são 
incluídas as bibliotecas do C, necessárias para executar as instruções ao longo 
do código. A linha 5 contém uma diretiva de pré-processamento, chamada 
elementos, ou seja, sempre que a palavra elementos for encontrada ao longo 
do código, ela será substituída pelo valor 7.
A diretiva de pré-processamento #define é um artifício utilizado antes da compilação 
para simplesmente substituir um elemento por outro. A sintaxe do #define é:
A função main, declarada das linhas 31 a 43, forma um vetor com a quan-
tidade de elementos definida pela diretiva #define, e depois mostra esse vetor 
na tela. O próximo passo é a chamada para a função Quicksort, responsável 
por fazer a ordenação do vetor. No retorno dessa função, o main mostra o 
vetor ordenado.
A função Quicksort está declarada das linhas 7 a 29. Ela define o pivô 
como o elemento mais à esquerda do vetor e faz a comparação dele com cada 
um dos outros elementos do vetor, verificando se o elemento é menor do que 
ele. Se for menor, o elemento será guardado em uma variável, para que seja 
colocado na posição esquerda da lista.
Depois disso, a função Quicksort é chamada novamente de dentro dela 
mesma, por meio de recursividade, para que novas comparações sejam feitas. 
Esse processo é repetido até que o vetor esteja completamente ordenado.
Desta forma, a execução do programa mostra para o usuário a tela repre-
sentada na Figura 1.
5Ordenação de dados — métodos eficientes
Figura 1. Exemplo de ordenação pelo método Quicksort.
Método de ordenação Mergesort
O Mergesort que, traduzido do inglês, significa ordenação por meio de mis-
tura, é um dos mais conhecidos algoritmos de ordenação por comparação. 
Ele também utiliza a estratégia da divisão e conquista. Foi criado, em 1945, 
por Von Neumann, tendo como premissa básica, assim como o Quicksort, a 
técnica de resolver um problema inicial por sua divisão em problemas menores, 
até que todos os problemas estejam solucionados. Como o método Mergesort 
também utiliza recursividade, é possível que não seja a solução mais eficiente 
em alguns casos (AZEREDO, 1996).
O funcionamento básico do Mergesort consiste em ordenar uma lista de 
valores a partir de outras listas também ordenadas. Para que isso aconteça, o 
Mergesort precisa dividir o vetor original em vetores menores, a fim de que 
sejam ordenados e, depois, agrupados em sequências até que o vetor inicial 
esteja totalmente ordenado.
Em outras palavras, por meio do Mergesort um vetor inicial é dividido em 
duas partições ou subvetores, cada subvetor é ordenado de forma recursiva, 
inclusive sendo redividido, quando possível. Por último, é feito um merge, 
ou uma mistura, dos dois últimos subvetores para que o vetor original fique 
ordenado por completo. Esse processo é conseguido com o auxílio de um vetor 
auxiliar, de tamanho idêntico ao do vetor original, em que os resultados das 
ordenações serão guardados. Ao final, o conteúdo dos vetores auxiliares é 
transferido para o vetor de resposta, formado pela mistura dos dois últimos 
vetores (DEITEL; DEITEL, 2011).
Ordenação de dados — métodos eficientes6
Por meio da comparação entre o Mergesort e outros algoritmos de orde-
nação, baseados em divisãoe conquista, você pode observar que sua com-
plexidade é semelhante a do Quicksort. Por outro lado, quando o Mergesort 
é comparado a outros algoritmos de comparação e troca, como o Bubblesort, 
o Insertionsort e o Selectionsort, se mostra muito mais rápido e eficiente se 
utilizado em grandes listas de valores.
O Bubblesort, o Insertionsort e o Selectionsort são métodos de ordenação baseados 
em divisão e conquista, da mesma forma que o Quicksort e o Mergesort.
Para saber mais sobre esses algoritmos, acesse o link a seguir.
https://goo.gl/Qk6xUq 
Apesar da sua comprovada eficiência frente aos demais algoritmos que 
operam por divisão e conquista, uma das grandes desvantagens da utilização 
do Mergesort como método de ordenação, é que o algoritmo cria uma cópia 
do vetor, a cada vez que a recursividade é executada, o que pode sobrecarregar 
a memória e o desempenho final do algoritmo.
Para exemplificar o método de ordenação Mergesort, pode-se criar um 
arquivo em C, que sirva para ordenar uma lista de valores com 12 números. 
O código utilizado foi o seguinte:
7Ordenação de dados — métodos eficientes
https://goo.gl/Qk6xUq
Ordenação de dados — métodos eficientes8
No código apresentado, você pode ver, entre as linhas 1 e 3, a inclusão das 
bibliotecas do C, necessárias para executar as instruções ao longo do código. 
A linha 5 contém uma diretiva de pré-processamento chamada elementos 
com o valor 12.
A função main, declarada entre as linhas 49 e 61, forma um vetor com 
a quantidade de elementos definida pela diretiva #define, que randomiza 
valores para os elementos do vetor até 200 e, depois, mostra esse vetor na 
tela. O próximo passo é a chamada para a função Mergesort, responsável 
por fazer a divisão do vetor inicial em dois, enquanto for possível, por meio 
de recursividade. No retorno dessa função, o main mostra o vetor ordenado.
9Ordenação de dados — métodos eficientes
A função Mergesort, declarada entre as linhas 40 e 47, após fazer a divisão 
do vetor inicial em vários outros, chama a função merge, que está definida 
entre as linhas 10 e 38. Essa função é responsável por fazer a ordenação dos 
vetores menores e, entre as linhas 35 e 37, move os elementos do vetor auxiliar 
novamente para o vetor inicial.
Da forma como está, a execução do programa mostra para o usuário a tela 
ilustrada na Figura 2.
Figura 2. Exemplo de ordenação pelo método Mergesort.
Comparação entre métodos de ordenação 
simples e eficientes
O processo de ordenação consiste em rearranjar uma lista de elementos em 
uma determinada ordem. A ordenação serve para que se consiga recuperar os 
elementos do conjunto de forma facilitada. Em geral, os métodos ou algoritmos 
de ordenação podem ser classificados conforme critérios que consideram a 
utilização da memória e o acesso aos registros (AZEREDO, 1996).
Ordenação de dados — métodos eficientes10
Um algoritmo é um esquema elaborado para resolver um problema. Ele pode ser 
implementado por meio da utilização de uma sequência de valores, objetos ou ele-
mentos que possuam uma lógica, como uma linguagem de programação, a língua 
portuguesa, etc. 
Uma receita culinária é um bom exemplo de algoritmo, mesmo sem utilizar uma 
linguagem de programação, já que um algoritmo trata-se de algo que mostra um passo 
a passo, com procedimentos necessários para chegar até a resolução de um problema.
Na área da ciência da computação, um algoritmo de ordenação é algo que 
traça o passo a passo necessário para colocar em ordem os elementos de uma 
determinada lista de valores, a fim de que os dados dessa lista possam ser 
acessados e recuperados de maneira mais fácil (LOPES, 1999).
Existem muitos critérios para comparar algoritmos de ordenação, como 
você pode observar a seguir (HERBERT, 1996).
 � Velocidade de ordenação: está diretamente relacionada à quantidade de 
comparações e de trocas que ocorrem durante a execução do algoritmo.
 � Quantidade de comparações: envolve a quantidade de vezes em que 
um elemento do vetor é comparado com outro.
 � Quantidade de trocas: envolve a quantidade de vezes em que um 
elemento do vetor ocupa o lugar de outro, e é necessário que eles tro-
quem de lugar. 
Os métodos ou algoritmos de ordenação podem ser classificados em:
 � Métodos de ordenação interna: são aqueles nos quais todos os ele-
mentos que precisam ser ordenados cabem na memória principal, e 
qualquer registro pode ser acessado de maneira imediata. Os métodos de 
ordenação interna são classificados em métodos de ordenação simples, 
e métodos de ordenação eficientes.
 � Métodos de ordenação externa: são aqueles nos quais os elementos 
que precisam ser ordenados não cabem na memória principal, e os 
registros precisam ser acessados em bloco ou em forma sequencial.
11Ordenação de dados — métodos eficientes
Os métodos de ordenação simples são mais utilizados quando a lista de 
elementos a ser ordenada é pequena. Eles utilizam mais comparações e pos-
suem códigos de programação menores, mais simplificados e mais fáceis de 
entender. Veja os métodos de ordenação simples mais conhecidos a seguir.
 � Selectionsort: o seu funcionamento consiste em, a cada nova iteração 
com o vetor, selecionar o menor elemento de toda a lista e colocá-lo 
na posição mais à esquerda possível. Ele é muito simples e é bastante 
recomendado para conjuntos pequenos de elementos a serem ordenados. 
Suas etapas consistem em: encontrar o menor elemento do vetor, trocar 
a sua posição com a do primeiro elemento do conjunto, procurar o se-
gundo menor elemento, trocá-lo de posição com o elemento da posição 
dois, agir recursivamente até que a ordenação do vetor esteja completa.
 � Insertionsort: nesse algoritmo, a premissa é analisar a lista de elementos 
um a um, da esquerda para a direita, inserindo-os em uma posição entre 
os elementos já tratados, ou seja, implica em arranjar um espaço novo 
entre os elementos do vetor. Esse algoritmo trabalha movendo um grande 
número de elementos para uma posição mais à direita. Os elementos 
à esquerda estão ordenados, mas não necessariamente se encontram 
na posição que vão estar ao final da ordenação, pois ainda podem ser 
deslocados para a direita, para dar lugar a elementos de valor menor 
que forem encontrados depois. Suas etapas consistem em selecionar um 
elemento e colocá-lo no seu lugar apropriado, que será definido pelo 
critério de ordenação. Esse método é recomendado para quando se sabe 
que o vetor está praticamente todo ordenado, ou para quando se deseja 
inserir alguns elementos em um conjunto de elementos já ordenado.
 � Bubblesort: é um dos algoritmos de ordenação mais utilizados, por ser 
um dos mais conhecidos. Sua ideia é fazer análises recursivas pelo vetor, 
trocando dois elementos a cada vez, desde que estejam fora de ordem, 
até que não haja mais trocas a serem feitas. Suas etapas consistem em 
percorrer o vetor analisando dois elementos que estejam lado a lado, 
trocar suas posições caso estejam fora de ordem e repetir esses passos 
até que não haja mais trocas a serem feitas. Esse algoritmo é lento na 
execução, pois compara duplas de elementos, o que o torna conhecido 
como o método mais ineficiente entre os métodos simples.
Ordenação de dados — métodos eficientes12
Já os métodos eficientes são mais recomendados quando a lista de elementos 
a ser ordenada é grande. Eles utilizam menos comparações, mas, em compen-
sação, precisam de um código de programação maior, mais complexo e mais 
detalhado para funcionar. Veja os métodos de ordenação eficientes a seguir.
 � Shellsort: é conhecido como um dos mais eficientes entre os métodos de 
ordenação, sendo uma extensão do método de ordenação Insertionsort. 
Em poucas palavras, o método consiste em percorrer, recursivamente, 
o vetor, dividindo-o em vetores menores. Nesses vetores menores, é 
aplicado o método Insertionsort. O Shellsort é um algoritmo rápido 
e eficiente que, geralmente, possui código de programação pequeno.
 � Quicksort: divide o vetor maior em vetores menores,que são ordenados 
de forma independente, para que sejam combinados a fim de produzir 
o resultado final da ordenação do vetor. É conhecido como o algoritmo 
mais rápido e que atende a uma grande variedade de situações. Suas 
etapas consistem em escolher um pivô para sinalizar onde o vetor será 
particionado, rearranjar os elementos menores ou iguais ao pivô em um 
dos lados e rearranjar os elementos maiores que o pivô no outro lado.
 � Heapsort: é um algoritmo com tempo de execução muito bom, e uso 
de memória reduzido. Ele utiliza uma estrutura de dados que se chama 
heap, que pode ser semelhante a uma árvore binária ou um vetor, que 
serve para ordenar os elementos, à medida que eles vão sendo inseridos 
na estrutura. Quando todos os elementos tiverem sido inseridos na 
heap, eles poderão ser removidos, na ordem desejada. Se o objetivo for 
implementar uma ordenação decrescente, o menor elemento da lista 
deve ser a raiz da heap; se o objetivo for implementar uma ordenação 
crescente, o maior elemento da heap deverá ser a raiz. O Heapsort não 
é recomendado para a ordenação de listas de valores pequenas, pois o 
tempo de construção da heap é alto e o algoritmo é bastante complexo, 
se comparado a outros métodos de ordenação. 
 � Mergesort: esse algoritmo também divide o problema maior em pro-
blemas menores, ordenando cada parte para depois fazer o merge, ou a 
mistura dos resultados. O vetor inicial é dividido em duas partes iguais, 
que depois serão divididos em outras duas partes e, assim, recursiva-
mente, até que a ordenação seja simples de resolver. Quando o merge 
é feito, as partes ordenadas são separadas, e o menor elemento de cada 
conjunto é selecionado e retirado dele. Os menores entre os elementos 
restantes são comparados, até que se consiga juntar as partes e o vetor 
esteja completamente ordenado.
13Ordenação de dados — métodos eficientes
Existem três métodos de ordenação de vetores: por troca, por seleção e por inserção. 
Esses métodos podem ser entendidos, de maneira didática, imaginando-se a neces-
sidade de ordenar as cartas de um baralho, veja a seguir (HERBERT, 1996).
 � Por troca: espalhar as cartas em uma mesa, voltadas para cima e trocar as cartas 
fora de ordem, até que todo o baralho fique ordenado.
 � Por seleção: espalhar as cartas na mesa, selecionar a carta de menor valor e segurá-la 
na mão. repetir esse processo até que todas as cartas estejam ordenadas na sua mão.
 � Por inserção: segurar todas as cartas na mão, colocar uma carta por vez sobre a 
mesa, sempre a inserindo na posição correta, repetidas vezes, até que não sobre 
mais cartas na mão.
AZEREDO, P. A. Métodos de classificação de dados e análise de suas complexidades. Rio 
de Janeiro: Campus, 1996.
DEITEL, P. J.; DEITEL, H. M. C: como programar. 6. ed. Rio de Janeiro: Pearson, 2011.
HERBERT, S. C: completo e total. São Paulo: Makron Books, 1996.
LOPES, A. V. Estruturas de dados: para a construção de software. Canoas: Ulbra, 1999.
Ordenação de dados — métodos eficientes14
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.