Aula 041669038801

ALGORITMOS DE ORDENAÇÃO EFICIENTES
Estudaremos os algoritmos de ordenação eficientes. Em outras palavras,

aqueles capazes de realizar uma tarefa consumindo o mínimo de recursos e
cometendo o menor número de erros possíveis.
Embora alguns algoritmos já estudados como o de inserção, seleção ou por
bolha possam ser úteis na ordenação de estruturas de dados complexas; eles só
promovem uma eficiência aceitável em estruturas como array e listas pequenas.
Os vetores são estruturas com grandes quantidades de informação, portanto
algoritmos mais simples não são eficientes o suficiente para ordená-los. Para estes
casos é necessária a aplicação de ferramentas mais complexas.
É importante lembrar que um algoritmo é uma construção lógica usada para
resolver determinados problemas. Por sua vez, um algoritmo de ordenação tem a
finalidade de organizar elementos de uma estrutura de dados, normalmente em ordem
crescente ou decrescente para facilitar buscas de informação.
O uso de algoritmos de ordenação é fundamental em diversas atividades dentro
da programação. Podemos citar como exemplo sua utilidade em bancos de dados,
dicionários eletrônicos, agendas telefônicas eletrônicas etc. (DEITEL; DEITEL, 2010).
Além disso, com a evolução da internet e o grande volume de informações
existentes, as estruturas de dados se tornaram tão complexas que a busca eficiente
de informações é somente possível com a implementação de algoritmos mais
sofisticados como o merge sort, quick sort, shell sort, counting sort e heap sort.
A escolha correta de qual algoritmo deverá ser usado em uma estrutura
depende da análise dos dados a serem consultados. Os métodos geralmente se
dividem em dois tipos que são as matrizes e os arquivos (sequenciais). As duas
classes, muitas vezes, são chamadas, respectivamente, de ordenação interna e
externa.
Isso acontece porque as estruturas internas são guardadas em áreas de
armazenamento de alta velocidade e de acesso aleatório como, por exemplo, a
memória principal do computador. Já a ordenação externa é realizada em objetos que
ficam armazenados em dispositivos de movimentação mecânica (discos e fitas).
Como essas estruturas dependem da velocidade de conexão, rotação e transferência
de dados entre a memória principal e o dispositivo, o seu acesso é mais lento.
Shell sort
O algoritmo de ordenação por inserção apresenta uma eficiência aceitável
somente em estruturas de dados pequenas. Quando aplicado em conjuntos maiores
ou mais complexos (que possuem elementos de valores menores posicionados nas
extremidades da estrutura), ele demora muito tempo para executar a tarefa. Isso
acontece, principalmente, porque a sua complexidade é determinada pelo termo
O(n²). Isso significa que o tempo exigido para a ordenação da matriz cresce mais
rápido que o seu tamanho. (NASCIMENTO; MOZZAQUATRO; ANTONIAZZI, 2016).
Em 1959, Donald Shell introduz o algoritmo shell sort (também conhecido como
diminuição do incremento) que apresenta uma eficiência aceitável em estruturas
maiores. Esse método de ordenação move os valores menores para um lado e os
maiores para o outro. Além disso, ao invés de organizar a matriz de uma única vez,
ele a subdivide em partes menores.
Figura – Movimentação dos elementos

Conceitualmente, a matriz principal é subdividida em diversas submatrizes e o
mesmo procedimento é implementado para cada uma delas individualmente. Essa
subdivisão é chamada de GAP e sua descoberta é o coração da ordenação shell.
Figura – Gap – divisão em submatrizes
Em resumo, pode-se dizer que o gap cria novas submatrizes dentro da matriz
principal.
Vamos a um exemplo prático. Suponhamos a seguinte matriz de 12 elementos
(10 8 6 12 6 5 0 1 4 3 9 11) cujo gap é n/2, ou seja, 12/2 = 6. Tem-se, então, os valores
10, 0, 11 que representam respectivamente as posições zero, seis e onze da matriz.
Desta forma, temos:
Figura – Matriz inicial
Como 10 > 0, acontece a primeira troca:

Figura – Matriz com GAP = 6
Como 11 > 10, a matriz se mantém:
Figura– Matriz sem alteração
Nesse momento, o GAP é dividido em duas partes, ou seja, GAP= 6/2 = 3. Tem-
se agora os números 0, 12, 10, 3 e 11 com índices das submatrizes resultantes.
Após o descobrimento do novo GAP, torna-se possível fazer a comparação dos
elementos mais espaçados. Esse processo continua até que as trocas de posição
sejam feitas por elementos adjacentes. Além disso, nada impede que, após o primeiro
GAP ser determinado, se aplique outros métodos de ordenação às submatrizes como,
por exemplo, o método de inserção.
Análise do algoritmo
Agora vamos ilustrar na prática o uso do algoritmo shell sort por meio da sua
implementação na linguagem Java, ordenando uma estrutura de dados array de nove
elementos do tipo inteiro.
Figura – Algoritmo de ordenação shell
Nota-se a utilização de comandos de repetição e de decisão no código para

analisar as submatrizes e determinar o incremento. Esse algoritmo é um pouco mais
complexo do que o de ordenação simples.
As declarações fundamentais do algoritmo são realizadas nas linhas 26, 27, 28
e 29. De maneira mais específica, nós temos a criação da matriz na linha 26; a
determinação do método de ordenação sort() na linha 27; e a exibição de todos os
elementos, agora devidamente ordenados, na linha 28.
Na linha cinco, o método sort() recebe uma matriz com parâmetro. Na linha
sete, é determinado o tamanho do GAP. O loop mais externo controla o incremento
que é decrementado na linha 23. O loop mais interno tem a finalidade de fazer as
trocas.
O aspecto fundamental desse algoritmo é a divisão da matriz em submatrizes.
Os resultados trazidos pela ordenação de shell são melhores que qualquer algoritmo
de ordenação simples.
Complexidade
A complexidade desse algoritmo é de O(n log n)^2) tanto no pior quanto no
melhor caso.
Counting sort
O algoritmo de ordenação por contagem conta a frequência com que cada
número ocorre na matriz. Em seguida, armazena esses contadores em uma matriz
auxiliar. (ELKAHLOUT; MAGHARI, 2017).
Esse algoritmo é baseado em chaves específicas. Além disso, como uma nova
matriz auxiliar é criada, pode-se classificá-lo como not-in-place.
Figura – Algoritmo counting sort
A cada inserção de um novo elemento Y na matriz X, é feita uma contagem e

verificação de todos os elementos menores que Y para posicioná-lo depois deles.
Suponhamos, por exemplo, a entrada do valor 10 em uma matriz de vinte
elementos onde existem cinco ocorrências menores que ele. Neste caso, o valor 10
seria movido para a posição 5 da matriz, após os cinco elementos menores que ele.
Vamos a uma representação conceitual:
Figura – Matriz principal
Para a aplicação do algoritmo, é criada uma matriz auxiliar de contagem com o

maior valor encontrado na matriz principal. Como o número mais alto da nossa matriz
de dez elementos é o sete, a nova matriz terá oito elementos que representam as
posições de zero a sete.
Figura – Matriz de contagem
Nota-se que a matriz de contagem é composta de elementos e de valores que

representam quantas vezes esse número apareceu na matriz principal. Por exemplo,
o índice zero aparece uma vez na matriz principal, por isso é representado pelo
número um. Os valores dois, quatro e seis, por outro lado, não aparecem nenhuma
vez, desta forma são representadas por um zero.
Agora, uma nova matriz é criada acumulando o número de ocorrências da
matriz de contagem.
Figura – Matriz acumulativa

Verifica-se que os valores dessa nova matriz são resultado da soma dos índices
anteriores. Por exemplo, no índice um (segunda colocação na tabela), soma-se o valor
da posição que o precede com a sua frequência na matriz principal. Desta forma,
temos: (valor do índice 0) + (número de vezes que 1 se repete) = (valor do índice 1 na
matriz acumulativa). Ou seja. 1 + 2 = 3
Na posição seguinte, como o número dois não aparece nenhuma vez na
tabela, apenas repete-se o valor da colocação anterior (3+0=3).
Em seguida, a partir da sua última posição, cada índice da matriz principal é
colocado em uma posição temporária para, posteriormente, ser movido para o seu
lugar correto na tabela principal. Observe a figura a seguir:
Figura – Conceito do algoritmo de counting sort
Inicialmente, o algoritmo seleciona o valor da última posição da matriz A (Neste

caso 3). Em seguida, procura o índice correspondente à colocação três na matriz B
(Neste caso 5). Depois, posiciona esse valor (3) na quinta posição (corresponde ao
número 4, pois a tabela conta o 0) da matriz C. Por fim, subtrai 1 do valor da posição
3 da matriz B que deixa de ser 5 e passa a ser 4.
Esse processo se repete, desta vez, usando o valor da penúltima posição da
matriz principal e o loop se mantém até que os dados fiquem perfeitamente ordenados
dentro da matriz temporária, posteriormente eles são transferidos para a matriz
principal, seguindo sempre da direita para a esquerda.
Análise do algoritmo
Agora, vamos ilustrar na prática o uso do algoritmo de ordenação por contagem
por meio da sua implementação na linguagem Java, ordenando uma estrutura de
dados array de nove elementos do tipo inteiro.
Figura– Algoritmo de ordenação de counting sort
Nota-se no algoritmo que as linhas nove e dez determinam respectivamente as

declarações da matriz e do maior valor. Na linha 12, o método de ordenação é
declarado por meio de dois parâmetros.
O método possui dois comandos de repetição. No primeiro, a matriz de
contagem é criada e no segundo, os termos são ordenados. Na linha 14, a matriz é
exibida em ordem.
Esse método de ordenação cria uma matriz de contagem linear que se estende
até o valor máximo da estrutura. Isso pode ser prejudicial quando, pelo menos, um
dos elementos a ser ordenados possui um valor muito elevado como, por exemplo,
M[1,2,3,500,2000]. Por outro lado, a eficiência aumenta quando os elementos são
pequenos, mesmo que a matriz seja extensa. Isso ocorre porque o algoritmo passa
por todos os elementos da tabela.
Complexidade
A complexidade é linear. Tanto o pior quanto o melhor dos casos são iguais. O
termo usado é O(n+k).
Heap sort
O uso de um algoritmo por seleção para ordenar uma estrutura de dados resulta
em O(n2) operações. Por conta disso, perde-se muita eficiência ao aplicá-lo para
organizar uma grande quantidade de índices. (DEITEL; DEITEL, 2010).
O método heap faz uso de uma abordagem de ordenação por seleção. Desta
forma, ele escolhe o elemento que precede todos os outros, logo em seguida, o
segundo (n-1) e assim consecutivamente até a ordenação completa da matriz
(AREMU et al., 2013).
Em uma ordenação crescente, o maior elemento é colocado no final da matriz,
o segundo maior é posicionado antes dele e assim até que todos os valores estejam
em ordem. Esse padrão de comportamento é oposto ao da ordenação por seleção
que começa pelo início (lado esquerdo da matriz), selecionando os elementos
menores.
Heap é uma árvore binária com duas propriedades fundamentais:
• O valor principal não é maior que os nós filhos;
• Ocorre um balanceamento e as folhas no último nível estão posicionadas
mais à esquerda.
Figura– Árvore binária
Em uma estrutura de dados complexa como a árvore, os elementos de uma

heap não ficam ordenados. Desta forma, o único comando é que o valor do elemento
no nó raiz seja maior que os presentes nos nós filhos.
A ordenação de uma matriz heap acontece de baixo para cima (bottom up) e
tem concentração maior no lado esquerdo.

Aula 041669038801

Enviado por

Direitos autorais:

Formatos disponíveis

Aula 041669038801

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aula 041669038801

Enviado por

Direitos autorais:

Formatos disponíveis

ALGORITMOS DE ORDENAÇÃO EFICIENTES

Estudaremos os algoritmos de ordenação eficientes. Em outras palavras,

Figura – Movimentação dos elementos

Figura – Gap – divisão em submatrizes

Figura – Matriz inicial

Como 10 > 0, acontece a primeira troca:

Como 11 > 10, a matriz se mantém:

Figura– Matriz sem alteração

Nota-se a utilização de comandos de repetição e de decisão no código para

Figura – Algoritmo counting sort

A cada inserção de um novo elemento Y na matriz X, é feita uma contagem e

Figura – Matriz principal

Para a aplicação do algoritmo, é criada uma matriz auxiliar de contagem com o

Figura – Matriz de contagem

Nota-se que a matriz de contagem é composta de elementos e de valores que

Figura – Matriz acumulativa

Figura – Conceito do algoritmo de counting sort

Inicialmente, o algoritmo seleciona o valor da última posição da matriz A (Neste

Figura– Algoritmo de ordenação de counting sort

Nota-se no algoritmo que as linhas nove e dez determinam respectivamente as

Em uma estrutura de dados complexa como a árvore, os elementos de uma

Você também pode gostar