UNIDADE 15 Ordenação de Dados

Prévia do material em texto

Ordenação de Dados
APRESENTAÇÃO
Nesta Unidade de Aprendizagem, estudaremos o funcionamento de alguns métodos de 
ordenação interna de dados, seu funcionamento básico e o que as diferencia, para, assim, 
identificar as vantagens e desvantagens da utilização em uma aplicação na qual se faz necessária 
a ordenação dos dados armazenados. 
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Diferenciar alguns dos métodos de ordenação interna de dados.•
Reconhecer o funcionamento de alguns dos métodos de ordenação interna de dados.•
Identificar os benefícios da aplicação da ordenação de dados na solução de problemas do 
dia a dia.
•
DESAFIO
Muitos são os métodos de ordenação de dados internos. As técnicas de ordenação permitem ter 
várias derivações de algoritmos distintos para resolver a mesma tarefa. Para escolher o método 
mais eficiente de ordenação de dados para o problema em questão, é necessário avaliar vários 
itens, tais como: 
► Como os dados estão originalmente: em ordem? A ordem é 
aleatória, ascendente ou descendente? 
► Qual a quantidade de elementos a serem ordenados?
Para escolher o método mais eficiente, é necessário analisar todas as perguntas realizadas acima 
e observar em que situação um método é mais eficiente que outro. Nem sempre o método mais 
complexo, que utiliza estruturas complexas, é o mais eficiente. 
 
O método de ordenação bolha é um dos mais fáceis e simples e apresenta várias derivações de 
implementações. Você encontra uma simulação desse método, utilizando cartas de um baralho, 
no vídeo da dica do professor nesta unidade de aprendizagem. 
plemente uma solução para o método bolha observando os seguintes aspectos:
► Ordene do menor para o maior, colocando os elementos na ordem 
crescente;
o teste deve iniciar do lado direito do vetor, testando primeiramente os dois últimos elementos 
adjacentes no vetor;
na primeira interação, o menor elemento deve permanecer na primeira posição do vetor já 
ordenado.
► Abra o arquivo desenvolvido no VisuAlg no link abaixo:
 
Conteúdo interativo disponível na plataforma de ensino!
 
No arquivo encontram-se já implementados os módulos para a leitura e a impressão das cartas 
do baralho. Acrescente nesse mesmo arquivo o módulo de ordenação bolha e entregue o arquivo 
com a extensão .alg no link abaixo. 
INFOGRÁFICO
O esquema mostra os principais temas que serão abordados nesta Unidade.
CONTEÚDO DO LIVRO
Muitas são as formas existentes para ordenar valores, nomes, números, de forma crescente ou 
decrescente. Nem sempre o método mais complexo é o mais eficiente, pois depende da 
quantidade de dados que se deseja ordenar, assim como, a ordem original em que eles se 
encontram. Desta forma, precisamos conhecer os métodos existentes e saber escolher qual o 
melhor método, suas vantagens e desvantagens, para assim escolher o mais eficiente para a 
aplicação.
Boa leitura.
Conteúdo:
ALGORITMOS E 
PROGRAMAÇÃO
Neiva Kuyven
ORDENAÇÃO
DE DADOS
4
INTRODUÇÃO
Olá!
Neste texto você vai estudar os principais algoritmos de ordenação de dados 
existentes na literatura. Primeiramente, serão abordados esses algoritmos de 
forma conceitual, a fim de prover o entendimento da importância e a utilidade 
dos algoritmos de ordenação de dados. Posteriormente será apresentada 
uma análise do funcionamento peculiar de cada um dos algoritmos, ilustrando 
o seu funcionamento através de exemplos didáticos. Por fim, ainda neste 
capítulo, serão apresentadas estratégias para identificação do algoritmo de 
ordenação de dados mais adequado a cada contexto.
OBJETIVOS DE APRENDIZAGEM 
Ao final desta unidade você deve apresentar os seguintes aprendizados:
• Diferenciar alguns dos métodos de ordenação interna de dados.
• Reconhecer o funcionamento de alguns dos métodos de ordenação
interna de dados.
• Identificar os benefícios da aplicação da ordenação de dados na solução
de problemas do dia a dia.
PRINCIPAIS ALGORITMOS DE ORDENAÇÃO DE DADOS
Ao visualizarmos a pluralidade na sentença algoritmos de ordenação de 
dados, podemos facilmente nos questionar sobre o motivo da existência de 
mais de um algoritmo destinado ao mesmo fim. Isto porque cada algoritmo 
possui suas características peculiares, contudo, todos têm um único e 
principal objetivo, que é ordenar de maneira correta os dados. Nesta seção 
será analisado cada um dos métodos de ordenação para que, ao final deste 
estudo, você esteja apto a diferenciar os métodos de ordenação de dados.
ORDENAÇÃO POR BOLHA (BUBBLE SORT)
Dentre todos, este é o algoritmo com o funcionamento mais simples de 
entender e de implementar. A sua estrutura básica consiste na comparação 
de um elemento com o elemento do índice imediatamente posterior e na 
verificação dos valores armazenados nos índices. Como exemplo, o objetivo 
5
deste algoritmo pode ser ordenar elementos de forma crescente, da esquerda 
para a direita. Na comparação, caso o valor da esquerda seja maior, o algoritmo 
de bolha efetua a troca dos elementos: (vetor[x] < vetor[x+1]).
Este algoritmo é indicado apenas para situações em que o arquivo que se 
deseja ordenar for pequeno, pois, devido a este algoritmo não otimizar as 
comparações e comparar em todos os casos todos os elementos do vetor, 
ele tem um desempenho inferior aos demais algoritmos. Veja, na imagem a 
seguir, que são necessárias doze iterações para ordenar um algoritmo de 5 
elementos, sendo que, caso o menor número estivesse no último elemento, 
seriam necessárias pelo menos 25 iterações, uma vez que a complexidade do 
algoritmo é exponencial.
 
Nova verificação ao final, para conferir se 
todos estão realmente ordenados...
Figura 1 - Execução do algoritmo de bolha
6
ORDENAÇÃO POR SELEÇÃO (SELECTION SORT)
Neste exemplo, o algoritmo tem por objetivo colocar o menor número na 
primeira posição do vetor. Diferente do bubble sort, que percorre todo o vetor 
comparando pares de elementos, o selection sort seleciona um elemento e o 
compara com todos os valores do vetor, verificando se ele é o menor. Contudo, 
a ordenação por seleção, assim como a ordenação por bolha, não possui um 
bom desempenho para grandes trabalhos de ordenação. Veja, na ilustração a 
seguir, as etapas necessárias para ordenar o vetor utilizando o algoritmo de 
ordenação por seleção.
Figura 2 - Execução do algoritmo por seleção
7
ORDENAÇÃO RÁPIDA (QUICKSORT)
O algoritmo de ordenação Quicksort, como já diz o próprio nome, é o que 
possui a melhor eficiência e, por isso, maior velocidade na ordenação de 
grandes arquivos.
 
OUTROS ALGORITMOS DE ORDENAÇÃO DE DADOS
Além dos algoritmos já vistos (ordenação por bolha, ordenação por seleção e 
ordenação rápida), existem outros algoritmos de ordenação de dados, como 
o de ordenação por inserção (Insertion Sort) e o de ordenação por intercalação 
(Merge Sort).
Insertion Sort: Consiste em inserir o elemento já em sua posição correta; 
dessa forma, sempre que o algoritmo verificar que o elemento do índice 
imediatamente posterior (x+1) é inferior ao elemento do índice imediatamente 
anterior (x), além de efetuar a troca entre estes dois elementos, também irá 
verificar se algum dos elementos anteriores é maior e, então, inserir o valor 
no local adequado. Por exemplo:
[5] [8] [7] [6] [3] - Vetor inicial.
8
[5] [8] [7] [6] [3] – O algoritmo seleciona o primeiro elemento, no caso, o 
número 5 e compara com o elemento imediatamente posterior, no caso, o 
elemento 8. Como 5 < 8, não é efetuada nenhuma troca.
[5] [8] [7] [6] [3] – O algoritmo seleciona o segundo elemento, no caso, o 
número 8 e compara com o elemento imediatamente posterior, no caso, o 
elemento 7. Como 8 > 7, é efetuada a troca entre eles. Contudo, antes de 
inserir o 7 em sua nova posição, o programa vai verificar se o elemento à 
esquerda do 8 é inferior ao 7; como é inferior, apenas insere o 7. 
[5] [7] [8] [6] [3] – O algoritmo seleciona o terceiro, no caso, o número 8 e 
compara como elemento imediatamente posterior, no caso, o elemento 6. 
Como 8 > 6, é efetuada a troca entre eles. Contudo, analisando o elemento 
imediatamente anterior ao 8, que é o 7, verifica-se que 7 é maior que 6 e, por 
isso, é feita nova troca.
[5] [6] [7] [8] [3] – O algoritmo testa o quarto elemento, no caso, o 8. Como 
o elemento imediatamente posterior contém o valor 3, é efetuada a troca. 
Contudo, o valor 3 também é inferior aos elementos anteriores ao 8 (7, 6, 3 
e 5) e, por isso, são efetuadas novas trocas até que o valor 3 chegue no seu 
lugar. Após três novas trocas, o vetor ficará assim: [3] [5] [6] [7] [8].
Merge Sort: Este algoritmo usa a estratégia de dividir para conquistar, ou seja, 
divide o vetor em partes e ordena dentro de cada parte. Veja o exemplo a 
seguir:
[5] [3] [2] [4] [7] [1] [0] [6] - Formação inicial do vetor.
[5][3][2][4] [7][1][0][6] - O vetor é dividido em dois grupos.
[5][3] [2][4] [7] [1] [0] [6] - O vetor é novamente dividido, agora em quatro 
grupos, atingindo, assim, a máxima divisão possível.
[3][5] [2][4] [1][7] [0][6] – O algoritmo realiza a ordenação de cada grupo.
[3][5][2][4] [1][7][0][6] - O algoritmo realiza um reagrupamento.
[2][3][4][5] [0][1][6][7] - O algoritmo realiza a ordenação nos subgrupos 
maiores através da comparação dos primeiros elementos de cada grupo 
menor.
9
Veja a sequência de passos para ordenação entre os grupos:
[2] [3][4][5] [0] [1][6][7] - Comparação do primeiro elemento do primeiro 
grupo com cada elemento do segundo grupo. Se algum dos elementos do 
segundo grupo for menor que o primeiro elemento do primeiro grupo, é feita 
a troca de posição. Ao final de todas as trocas tem-se o vetor ordenado.
[0] [1] [2] [3] [4] [5] [6] [7] 
15
REFERÊNCIAS
HONORATO, Bruno de Almeida. Algoritmos de Ordenação – Análise e 
Comparação. Disponível em: <http://www.devmedia.com.br/algoritmos-de-
ordenacao-analise-e-comparacao/28261>. Acesso em: 02 jan. 2017.
SANTOS, Tiago. Bubble Sort. Disponível em: <https://www. 
youtube.com/watch?v=llX2SpDkQDc>. Acesso em: 02 jan. 2017.
SANTOS, Tiago. Insertion Sort. Disponível em: 
<https://www.youtube.com/watch?v=-Z00it6Nkz8>. Acesso em: 
02 jan. 2017.
SANTOS, Thiago. Merge Sort. Disponível em: <https://www. 
youtube.com/watch?v=cDNqk4tdvqQ>. Acesso em: 02 jan. 2017.
SANTOS, Tiago. Selection Sort. Disponível em: <https://www. 
youtube.com/watch?v=BSXIolKg5F8>. Acesso em: 02 jan. 2017.
SAIBA+
Conteúdo:
DICA DO PROFESSOR
Em muitas atividades do nosso dia a dia, necessitamos consultar dados que se encontram já 
ordenados. Como exemplo, pode-se citar uma consulta a uma lista telefônica, em que a 
atividade de pesquisar e encontrar o número do telefone de uma pessoa seria muito árdua se a 
lista não estivesse organizada por cidades e por nome. Na computação, uma das atividades 
muito utilizadas é a ordenação de dados, pois pesquisamos muitas informações armazenadas em 
computadores espalhados pelo mundo inteiro. Conhecer o funcionamento dos métodos é muito 
importante para a escolha do algoritmo de ordenação para a sua aplicação. Assista ao vídeo para 
conhecer um pouco mais sobre a ordenação de dados e o funcionamento do método bolha, 
considerado um dos métodos mais simples.
Conteúdo interativo disponível na plataforma de ensino!
EXERCÍCIOS
1) Com base na funcionalidade dos métodos internos simples de ordenação de dados, 
identifique qual o método corresponde a cada alternativa descrita abaixo.I. A 
________________ seleciona o menor entre os n elementos de um vetor ou uma tabela 
e realiza a troca deste pelo primeiro elemento. E, para o restante dos elementos, é 
encontrado novamente o elemento de menor chave, trocando-o pelo segundo 
elemento e assim por diante até chegar aos dois últimos elementos.II. A 
_________________ percorre elemento por elemento do vetor ou tabela, deslocando 
os elementos já ordenados e inserindo o elemento que deseja colocar em ordem na 
posição correta com relação aos elementos já ordenados. III. A _________________ é 
a ordenação por trocas, que envolve repetidas comparações e, se necessário, a troca 
de dois elementos que encontram-se um ao lado do outro. Nesse método, o elemento 
mais leve sobe e o mais pesado desce, ou ocorre o contrário, dependendo da ordem na 
qual deseja-se colocar os elementos ordenados.Os métodos internos que representam 
de forma correta a sua funcionalidade descrita acima nas alternativas I, II e III são, 
respectivamente: 
A) Ordenação por seleção – ordenação por inserção – ordenação bolha.
B) Ordenação por seleção – ordenação bolha - ordenação por inserção.
C) Ordenação por inserção – ordenação bolha - ordenação por seleção.
D) Ordenação bolha – ordenação por inserção – ordenação por seleção.
E) Ordenação por inserção – ordenação por seleção – ordenação bolha.
2) Em vários momentos do nosso dia a dia, precisamos de dados ordenados para agilizar 
nosso trabalho de pesquisa ou busca. Como exemplo, pode-se citar um relatório dos 
dados pessoais dos funcionários de uma empresa. Como seria consultar os dados de 
um funcionário, como e-mail ou telefone, se o relatório não estivesse em ordem 
alfabética de nome? Em função dessa necessidade de dados ordenados, existem vários 
métodos de ordenação, alguns melhores que outros. Analise e julgue as alternativas a 
seguir, acerca dos algoritmos para ordenação interna apresentados na Unidade de 
Aprendizagem. I. O algoritmo de ordenação por inserção simples apresenta um 
ótimo desempenho quando os elementos a serem ordenados encontram-se já inseridos 
de forma ordenada, não importando a quantidade de elementos a serem ordenados. 
Apresenta um desempenho não eficiente se os elementos encontram-se em ordem 
descendente/invertida.II. Um algoritmo de ordenação é considerado estável se ele não 
alterar a posição relativa de elementos de mesmo valor.III. O método bolha é um dos 
métodos mais fáceis de programar, mas não é eficiente comparado a outros 
métodos.IV. Os métodos de ordenação simples por inserção, método bolha e por 
seleção possuem complexidade de O(n2) comparações.Assinale a alternativa que 
contém a correta sequência de V (verdadeiro) e F (falso), correspondente às 
afirmativas acima. 
A) V, V, F, V.
B) V, F, V, F.
C) F, V, F, V.
D) V, V, V, F.
E) V, V, V, V.
3) Com relação à classificação dos métodos de ordenação e de fatores que devem ser 
levados em consideração no momento de avaliar e comparar os diversos métodos 
estudados na Unidade de Aprendizagem, avalie as alternativas apresentadas abaixo e 
assinale a alternativa INCORRETA. 
A) Os métodos de ordenação são classificados em interno, externo e misto.
B) O número de comparações entre as chaves e o número de trocas entre os elementos para a 
sua ordenação não podem ser considerados uma forma de avaliar e comparar os métodos 
de ordenação interna estudados na Unidade porque cada algoritmo é diferente.
C) O método de ordenação é considerado estável quando, no momento da ordenação, não 
movimenta os elementos que são iguais, ou seja, que possuem a mesma chave.
D) O método possui um comportamento natural quando trabalha o mínimo, quando os 
elementos forem inseridos de forma ordenada; trabalha mais quando os elementos forem 
introduzidos de forma mais desordenada e trabalha o máximo quando em ordem inversa.
E) A ordenação tem por objetivo facilitar e agilizar a busca de elementos.
Considere o módulo de ordenação denominado ORDENA_VETOR desenvolvido em 
pseudocódigo:Realize o teste de mesa para o módulo ORDENA_VETOR com os 
valores de entrada para o vetor “Elementos” de 6 posições, em que o vetor é uma 
variável local do algoritmo.Elementos = {6,5,3,23,12,34} 
 
Representações: 
indice, f: representam os índices que controlam a posição do vetor Elementos. 
Elementos: representa o vetor no qual os elementos estão armazenados. 
4) 
tmp: representa uma variável auxiliar para a troca dos elementos de posição. 
menor: representaa variável que armazena a posição do menor elemento 
encontrado. 
Selecione a alternativa que representa o método de ordenação utilizado para ordenar 
o vetor Elementos. 
A) Ordenação bolha.
B) Ordenação por inserção.
C) Ordenação por seleção.
D) Quicksort.
E) Ordenação Shell.
O método de ordenação Quicksort é um dos métodos de ordenação interna mais 
eficiente em um grande número de situações práticas de aplicação em que a 
ordenação se fez necessária. O método apresenta diversas derivações de algoritmos 
para a implementação, algumas mais simples, outras utilizando a recursividade, que 
empregam a chamada funções de forma recursiva, ou seja, funções que chamam por 
elas mesmas. Como exemplo de aplicação, podemos citar a ordenação de nomes e 
notas de todos os alunos de uma turma da disciplina de Cálculo dos cursos de 
Engenharia em ordem alfabética de forma crescente ou decrescente ou em ordem de 
notas, conforme necessidade do professor.Com relação a esse método, analise as 
afirmações abaixo e marque qual apresenta informações INCORRETAS. 
I . O método Quicksort é considerado um método de ordenação estável. 
II. A escolha correta do pivô é essencial para a garantia de eficiência do algoritmo. O 
cálculo da mediana de três chaves é uma das formas eficientes de encontrar o 
elemento pivô. 
III. O pivô pode ser o elemento do meio do vetor/tabela a ser ordenado. 
5) 
IV. Utiliza um pivô para dividir o vetor/tabela em duas partes, em que vai colocando 
os menores elementos de um lado e os maiores de outro.
A) I.
B) I e II.
C) III e IV.
D) I, II e III.
E) I, II, III e IV.
NA PRÁTICA
A atividade de ordenação é uma das mais utilizadas na computação e é muito importante para 
todos nós. Consiste em uma atividade de organizar um conjunto de elementos em determinada 
ordem, podendo ser ascendente ou descendente, e que tem por objetivo principal facilitar e 
agilizar a busca ou recuperação de um elemento. 
Vamos analisar uma situação prática! 
 
Você teria que ler toda a lista telefônica para encontrar o nome da pessoa que deseja. A pesquisa 
seria realizada pela chave (nome). Assim, encontrando o registro, encontraria o número de 
telefone, mas isso aconteceria depois de dias de pesquisa.
Entretanto, como a lista telefônica vem classificada por categorias, e, dentro das categorias, vem 
ordenada por nome, com certeza encontraremos o telefone de maneira muito rápida.
Mas e se a lista viesse ordenada de outra forma?
Pegue a lista telefônica de sua cidade e verifique como ela está organizada. Hoje, todas as listas 
são eletrônicas. Mas pegue uma antiga e olhe. Já pensou se tivesse uma única lista para todos os 
telefones do mundo, ou de um país inteiro, ou de um estado inteiro para você procurar. Qual 
seria o tamanho dessa lista?
Com certeza, sua pesquisa levaria muitos dias para ter o retorno do número procurado, pois o 
número de elementos nos quais você pesquisaria aumentaria consideravelmente, aumentando 
também o tempo para encontrar um elemento dentro de uma tabela. A tabela estar ordenada ou 
não, e de que forma está ordenada, também são aspectos que facilitam ou complicam a nossa 
vida no momento da pesquisa.
Assim como essa, existem muitas outras aplicações, como:
►Agenda de compromissos ordenada por datas de compromissos. 
►Clientes ordenados por código ou nome. 
►Relatório da folha de pagamento ordenado por nome ou por 
salário. 
O gestor pode querer saber quem está ganhando mais e na ordem decrescente. 
►O professor quer a relação de alunos por ordem de média 
decrescente. 
Muitas são as aplicações, e praticamente tudo envolve ordenação para facilitar o tempo da busca 
de uma informação.
Para auxiliar a sua compreensão e a comparação entre alguns dos métodos de ordenação 
estudados, utilize o Simulador de Métodos de Ordenação para realizar testes com os dados de 
forma aleatória, decrescente e crescente.
No simulador, é possível testar:
 
 ►Um único método de ordenação isoladamente; 
 ►Todos os métodos em uma única forma de inserção de dados (em  
coluna); 
►um método com todos os tipos de entrada (em coluna); 
►todos os métodos e formas de entrada juntos. 
Acesse o SIMULADOR desenvolvido por Nícholas André Pinho de Oliveira. O link está 
disponível no Saiba+ desta unidade.
SAIBA MAIS
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do 
professor:
Métodos de Ordenação BUBBLE, INSERTION, SELECTION, SHELL, MERGE E 
QUICK SORT.
Veja no vídeo a seguir uma dinamica para aprofundar os conhecimentos sobre Bubble, 
Insertion, Selection, Shell, Merge e Quick Sort
Conteúdo interativo disponível na plataforma de ensino!
quicksort
Veja no vídeo a seguir um método de quicksort utilizando cartas para melhor compreensão
Conteúdo interativo disponível na plataforma de ensino!
Método de Inserção
veja o vídeo a seguir com maiores explicações a respeito do método de inserção
Conteúdo interativo disponível na plataforma de ensino!
Método de Ordenação Shell Sort
Veja o método de Shell Sort com um exemplo utilizando cédulas de dinheiro
Conteúdo interativo disponível na plataforma de ensino!