UNIDADE 16 Aplicação de Ordenação de Dados

Prévia do material em texto

Aplicação de Ordenação de Dados
APRESENTAÇÃO
Nesta unidade, será feito estudo da análise e implementação de propostas de algoritmos de 
alguns métodos de ordenação interna de dados, por meio do seu desenvolvimento em 
pseudocódigo no Visualg.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Diferenciar soluções de implementação de alguns métodos de ordenação interna de dados 
em pseudocódigo.
•
Avaliar a implementação e o funcionamento de alguns métodos de ordenação interna de 
dados em pseudocódigo.
•
Aplicar a ordenação de dados na solução de problemas práticos.•
DESAFIO
A ordenação é o processo de arranjar um conjunto de informações semelhantes em uma ordem 
crescente ou decrescente. Para isto, existem muitos métodos de ordenação utilizados na 
computação para ordenar dados armazenados, assim como existem muitos algoritmos diferentes 
para cada método. O Bubble Sort (ou método bolha) é um dos métodos de ordenação mais 
conhecidos, mas é uma das piores ordenações entre os métodos. A ordenação bolha é uma 
ordenação por trocas, envolvendo repetidas comparações e, se necessário, a troca de dois 
elementos adjacentes. O nome bolha se deve ao fato de seu funcionamento ser igual ao de uma 
bolha, em que, ao se comparar os elementos para a troca, os valores mais leves ou menores 
sobem (início) e os mais pesados ou maiores descem (final) no vetor, ou o contrário: ao se 
ordenar de forma decrescente, as bolhas encontram o seu lugar.
O número de comparações do método bolha não reduz, mesmo os valores já sendo inseridos na 
ordem ou estarem ordenados no momento da ordenação, pois ele realiza os testes de 
comparações até o final do teste de todas interações com os seus elementos adjacentes. O 
algoritmo do método bolha básico pode ser melhorado. Uma proposta de implementação é testar 
se o vetor/tabela já se encontra ordenado, ou seja, se em uma determinada interação ele não 
realiza nenhuma troca para parar o processo de comparação, pois os elementos já se encontram 
em ordem, podendo esta ordem ser crescente ou decrescente.
A empresa quer dar um brinde para todos os seus funcionários e colocá-los em ordem crescente 
nas mesas do restaurante no momento do almoço. Auxilie a empresa Engenharia Tabajara Ltda. 
para otimizar o algoritmo de ordenação dos códigos de seus funcionários para serem 
classificados em ordem crescente, para, desta forma, serem impressos em ordem e colocados na 
mesa no momento do almoço no restaurante da empresa. A empresa possui 1.500 funcionários, 
mas, para o estudo, serão utilizados somente 10, com o intuito de simplificar e facilitar os testes 
do algoritmo em anexo.
Abra e analise o algoritmo no link a seguir desenvolvido no Visualg e desenvolva a nova 
proposta de otimização do algoritmo do método bolha apresentado anteriormente, para que ele 
pare as comparações quando o algoritmo já se encontrar ordenado e também para que ele conte 
e imprima quantas trocas de elementos realizou.
Clique neste Link para abrir o arquivo da empresa Tabajara Telecomunicações, em que já se 
encontra a implementação da leitura dos códigos dos funcionários (considerando somente 10 
códigos para o teste) :
Conteúdo interativo disponível na plataforma de ensino!
 
 
Também responda no espaço a seguir os seguintes questionamentos com relação ao número de 
comparações realizadas no método atual da empresa (sem alteração) e a nova proposta do 
algoritmo bolha:
a) Quantas comparações e trocas serão realizadas no algoritmo em anexo (sem alteração)? 
Utilize para o teste os códigos a seguir.
Códigos: {45, 67, 69, 300, 450, 100, 1450, 1500, 98, 70}
Qual é o número de comparações realizadas para ordenar os códigos?
Quantas trocas de elementos ele realiza para ordenar os códigos?
b) Quantas comparações serão realizadas no algoritmo novo implementado com a nova 
proposta de parar quando já estiver ordenado? Utilize para o teste os códigos a seguir.
Códigos: {45, 67, 69, 300, 450, 100, 1450, 1500, 98, 70}
Qual é o número de comparações realizadas para ordenar os códigos?
Quantas trocas de elementos ele realiza para ordenar os códigos?
c) Entregue a seguir a nova proposta do método bolha desenvolvido no espaço reservado 
para anexar o arquivo ALG do Visualg. Neste algoritmo, deverá ser implementada a nova 
proposta de melhorar o algoritmo bolha e também é preciso que o algoritmo conte e 
imprima quantas trocas de elementos ele realiza para ordenar os códigos anteriormente 
descritos.
INFOGRÁFICO
O esquema mostra os principais temas que serão abordados nesta unidade.
 
CONTEÚDO DO LIVRO
Para melhor compreender as soluções de implementação de alguns métodos de ordenação 
interna, acompanhe um trecho da obra "Algoritmos e Programação com exemplos em Pascal e 
C" de Nina Edelweiss. O livro servirá de base para a esta unidade de aprendizagem. Neste 
capítulo, serão apresentadas propostas de implementação de alguns algoritmos de ordenação de 
dados interna, como método bolha, método de seleção e quicksort com recursividade.
s
é
r
ie
 liv
ro
s
 d
id
á
tic
o
s
 in
fo
r
m
á
tic
a
 u
fr
g
s
23
s é r i e l i v r o s d i d á t i c o s i n f o r m á t i c a u f r g s
volume 3 Linguagens Formais e Autômatos, 6.ed., 
de Paulo Blauth Menezes
volume 4 Projeto de Banco de Dados, 6.ed., 
de Carlos Alberto Heuser 
volume 5 Teoria da Computação: Máquinas Universais 
e Computabilidade, 3.ed, de Tiarajú Asmuz Diverio 
e Paulo Blauth Menezes
volume 6 Arquitetura de Computadores Pessoais, 
2.ed., de Raul Fernando Weber
volume 7 Concepção de Circuitos Integrados, 2.ed., 
de Ricardo Augusto da Luz Reis e cols.
volume 8 Fundamentos de Arquitetura de Computadores, 
4.ed., de Raul Fernando Weber
volume 10 Tabelas: Organização e Pesquisa, 
de Clesio Saraiva dos Santos e Paulo Alberto de Azeredo 
volume 11 Sistemas Operacionais, 4.ed., 
de Rômulo Silva de Oliveira, Alexandre da Silva Carissimi 
e Simão Sirineo Toscani 
volume 12 Teoria das Categorias para Ciência 
da Computação, 2.ed., de Paulo Blauth Menezes 
e Edward Hermann Haeusler
volume 13 Complexidade de Algoritmos, 3.ed., 
de Laira Vieira Toscani e Paulo A. S. Veloso 
volume 16 Matemática Discreta para Computação 
e Informática, 4.ed., de Paulo Blauth Menezes
volume 18 Estruturas de Dados, de Nina Edelweiss 
e Renata Galante
volume 19 Aprendendo Matemática Discreta com 
Exercícios, de Paulo Blauth Menezes, Laira Vieira Toscani 
e Javier García López
volume 20 Redes de Computadores, 
de Alexandre da Silva Carissimi, Juergen Rochol 
e Lisandro Zambenedetti Granville
volume 21 Introdução à Abstração de Dados, 
de Daltro José Nunes
volume 22 Comunicação de Dados, de Juergen Rochol
COMPUTAÇÃO
www.grupoa.com.br
A Bookman é um dos selos editoriais do Grupo A Educação, empresa que 
oferece soluções em conteúdo, tecnologia e serviços para a educação 
acadêmica e profissional.
algoritmos
e programação 
com exemplos em Pascal e C
nina edelweiss
maria aparecida castro livi
Material didático para professores
Visite www.grupoa.com.br
nina edelweiss
maria aparecida castro livi
 l i v r o s d i s p o n í v e i s
algoritm
os e program
ação
com
 exem
plos em
 P
ascal e C
23
edelw
eiss
livi
23
algoritmos
e programação 
com exemplos em Pascal e C
Aprender programação não é uma tarefa simples. 
Requer um entendimento perfeito do problema, a análise 
de como solucioná-lo e a escolha da forma de implementação 
da solução. algoritmos e programação apresenta 
o processo de construção de algoritmos e de programas, 
enfatizando as etapas de abstração, organização, análise 
e crítica na busca de soluções eficientes. Os elementos 
de um programa são introduzidos pouco a pouco ao longo 
do texto, inicialmente apresentados em pseudolinguagem e, 
em seguida, exemplificados nas linguagens de programação 
Pascal e C. Este é um livro-texto para disciplinas iniciais 
de programação de duraçãode um semestre. Pode ser 
utilizado sobretudo em cursos de bacharelado e licenciatura 
em ciência da computação, análise de sistemas e engenharia 
da computação. 
E22a Edelweiss, Nina.
 Algoritmos e programação com exemplos em Pascal e C 
 [recurso eletrônico] / Nina Edelweiss, Maria Aparecida Castro 
 Livi. – Dados eletrônicos. – Porto Alegre : Bookman, 2014.
 Editado também como livro impresso em 2014.
 ISBN 978-85-8260-190-7
 1. Informática. 2. Algoritmos – Programação. I. Livi, 
 Maria Aparecida Castro. II. Título. 
CDU 004.421
 as autoras
Nina Edelweiss é engenheira eletricista e doutora em Ciência da Computação pela Uni-
versidade Federal do Rio Grande do Sul. Durante muitos anos, lecionou em cursos de Enge-
nharia e de Ciência da Computação na UFRGS, na UFSC e na PUCRS. Foi, ainda, orientadora 
do Programa de Pós-Graduação em Ciência da Computação da UFRGS. É coautora de três 
livros, tendo publicado diversos artigos em periódicos e em anais de congressos nacionais 
e internacionais. Participou de diversos projetos de pesquisa financiados por agências de 
fomento como CNPq e FAPERGS, desenvolvendo pesquisas nas áreas de bancos de dados e 
desenvolvimento de software.
Maria Aparecida Castro Livi é licenciada e bacharel em Letras, e mestre em Ciência da 
Computação pela Universidade Federal do Rio Grande do Sul. Desenvolveu sua carreira pro-
fissional na UFRGS, onde foi programadora e analista de sistema, antes de ingressar na 
carreira docente. Ministrou por vários anos a disciplina de Algoritmos e Programação para 
alunos dos cursos de Engenharia da Computação e Ciência da Computação. Sua área de 
interesse prioritário é o ensino de Linguagens de Programação, tanto de forma presencial 
quanto a distância.
Catalogação na publicação: Ana Paula M. Magnus – CRB 10/2052
Edelweiss_Iniciais_eletronica.indd iiEdelweiss_Iniciais_eletronica.indd ii 14/05/14 16:5114/05/14 16:51
180 Algoritmos e Programação com Exemplos em Pascal e C
exercício 6.8 Classificação por seleção. Esse é um método de classificação bastante sim-
ples, embora não muito eficiente. Para colocar os dados em ordem crescente, percorre-se 
o vetor buscando o elemento com o menor valor. Esse é trocado com aquele que está na 
primeira posição do vetor. O método é, então, repetido para o segmento do vetor que inicia 
na segunda posição, e assim sucessivamente. A Figura 6.6 mostra esquematicamente como é 
feita a classificação por seleção.
Algoritmo ClassSeleção
{CLASSIFICA UM VETOR PELO MÉTODO DE SELEÇÃO, EM ORDEM CRESCENTE}
 Constantes: MIN = 1
 MAX = 10 {LIMITES DO VETOR}
 Entradas:
 vet (arranjo [MIN..MAX] de inteiro) {VETOR A SER ORDENADO}
 Saídas: {VETOR CLASSIFICADO EM ORDEM CRESCENTE}
 Variáveis auxiliares:
 i, j (inteiro) {ÍNDICES DE UMA PASSADA}
 menor (inteiro) {MENOR VALOR DA PASSADA}
 aux (inteiro) {AUXILIAR PARA FAZER A TROCA}
início
 para i de MIN incr 1 até MAX faça
 ler (vet[i]) {PREENCHE VET POR LEITURA}
 para i de MIN incr 1 até MAX-1 faça
 início
 menor ← i
 para j de i+1 incr 1 até MAX faça
 se vet[j] < vet[menor]
 então menor ← j
 se menor ≠ i
 então início {VAI FAZER A TROCA}
 aux ← vet[i]
 vet[i] ← vet[menor]
 vet[menor] ← aux
 fim
 fim
 para i de MIN incr 1 até MAX faça
 escrever (vet[i]) {MOSTRA VET ORDENADO}
fim
exercício 6.9 Método da Bolha. Trata-se de um método de classificação de vetores bem 
mais eficiente do que o método de classificação por seleção antes apresentado. Consiste em 
percorrer o vetor comparando cada dois elementos adjacentes e trocando-os de posição caso 
estejam em ordem contrária à desejada. É feito um controle, a cada varredura do vetor, para 
saber se houve alguma troca de valores e, se houve, nova varredura é executada. O ponto 
onde a última troca aconteceu é fixado como o limite da próxima varredura, reduzindo pro-
gressivamente o número de elementos do conjunto considerado na varredura. Se nenhuma 
Edelweiss_06.indd 180Edelweiss_06.indd 180 12/03/14 09:0212/03/14 09:02
Capítulo 6 Variáveis Estruturadas: Arranjos Unidimensionais 181
troca acontece durante uma varredura, então o conjunto já está ordenado e o processo é 
interrompido. Essa estratégia recebe o nome de “Método da Bolha” (bubble sort) ou “orde-
nação por flutuação”, pois os valores maiores (no caso de ordenação em ordem crescente) 
vão “subindo” para o final do vetor a cada varredura, até atingirem sua posição definitiva no 
conjunto de dados.
A Figura 6.7 simula o funcionamento desse método para um vetor de cinco elementos intei-
ros. São representados os valores contidos no vetor nas três primeiras varreduras. Na quarta 
varredura, não será necessário troca – isso indica que o vetor está ordenado. Observar que, ao 
final da primeira varredura, o maior valor (30) estará na posição final e que os valores meno-
res terão descido uma posição, aproximando-se de sua posição correta. Na segunda varredura 
não é feita a comparação com o último valor, pois ele já está correto. Assim, a cada varredura 
diminui o tamanho do segmento de vetor a ser analisado.
O algoritmo apresentado a seguir classifica o vetor em ordem crescente. Se a ordena-
ção desejada for a decrescente, basta alterar a comparação de vet[i] > vet[i+1] para 
vet[i] < vet[i+1].
Algoritmo ClassBolha
{CLASSIFICA UM VETOR PELO MÉTODO DA BOLHA}
 Constante MAX = 5 {NÚMERO DE ELEMENTOS DO VETOR}
 Entradas:
 vet (arranjo [1..MAX] de inteiro) {VETOR A SER CLASSIFICADO}
 Saídas: {vet CLASSIFICADO}
 Variáveis auxiliares:
 i (inteiro) {ÍNDICE QUE PERCORRE O VETOR}
1 2 3 4 5
28 26 30 24 25
24 26 30 28 25
1 2 3 4 5
1 2 3 4 5
24 25 30 28 26
24 25 26 28 30
1 2 3 4 5
1 2 3 4 5
24 26 30 28 25
24 25 30 28 26
1 2 3 4 5
1 2 3 4 5
24 25 26 28 30
24 25 26 28 30
1 2 3 4 5
i=1
j=2 a 5 
i=2
j=3 a 5 
i=4
j=5 a 5 
i=3
j=4 a 5 
1ª iteração 2ª iteração
4ª iteração3ª iteração
figura 6.6 Classificação por seleção.
Edelweiss_06.indd 181Edelweiss_06.indd 181 12/03/14 09:0212/03/14 09:02
182 Algoritmos e Programação com Exemplos em Pascal e C
 k (inteiro) {AO TERMINAR A VARREDURA, ARMAZENA A POSIÇÃO
 ONDE OCORREU A ÚLTIMA TROCA}
 m (inteiro) {LIMITE SUPERIOR DA VARREDURA –
 RECUA UMA OU MAIS POSIÇÕES A CADA ITERAÇÃO}
 aux (inteiro) {VARIÁVEL AUXILIAR UTILIZADA PARA A TROCA}
 trocou (lógico) {VERDADEIRA SE OCORREU ALGUMA TROCA}
início
 para i de 1 incr 1 até MAX faça
 ler (vet[i]) {PREENCHIMENTO DO VETOR POR LEITURA}
 trocou ← verdadeiro {INICIALIZA trocou EM VERDADEIRO}
 m ← (MAX – 1) {INICIALIZA m NA PENÚLTIMA POSIÇÃO DO VETOR}
 k ← 1 {INICIALIZA k NO PRIMEIRO ELEMENTO DO VETOR}
 enquanto trocou {REPETE ENQUANTO HOUVER ALGUMA TROCA}
 início
 trocou ← falso {INDICA QUE NESTA VARREDURA AINDA NÃO HOUVE TROCA}
 para i de 1 incr 1 até m faça
 se vet[i] > vet [i + 1] {COMPARA VALORES ADJACENTES}
 então início
 aux ← vet[i] {TROCA DOIS ELEMENTOS DE POSIÇÃO}
 vet[i] ← vet [i + 1]
 vet[i + 1] ← aux
28 26 30 24 25
1ª iteração
26 28 30 24 25
26 28 30 24 25
26 28 24 30 25
26 28 24 25 30
26 28 24 25 30
26 28 24 25 30
26 24 28 25 30
26 24 25 28 30
26 24 25 28 30
2ª iteração
3ª iteração
24 26 25 28 30
24 25 26 28 30
figura 6.7 Classificação por meio do Método da Bolha.
Edelweiss_06.indd 182Edelweiss_06.indd 182 12/03/14 09:0212/03/14 09:02
Capítulo 6 Variáveis Estruturadas: Arranjos Unidimensionais 183
 k ← i {k POSIÇÃO EM QUE OCORREU A TROCA}
 trocou ← verdadeiro; {INDICA QUE NESTA VARREDURA HOUVE
 TROCA}
 fim
 m ← k {m INDICA ATÉ ONDE SERÁ FEITA A PRÓXIMA VARREDURA}
 fim {ENQUANTO}
 escrever ('Vetorclassificado');
 para i de 1 incr 1 até MAX faça
 escrever (vet[i]) {MOSTRA VETOR CLASSIFICADO}
fim
6.5 em Pascal
6.5.1 declaração de um vetor
Um tipo de dado vetor (arranjo de uma dimensão) é declarado em Pascal da seguinte forma:
array [<limite inferior>..<limite superior>] of <tipo>
Os limites superior e inferior, índices do primeiro e do último elemento do vetor, devem ser do 
tipo inteiro, caractere ou do tipo enumeração (que será apresentado no Capítulo 8). O 
tipo declarado no final será o tipo de todos os elementos do vetor.
Exemplo de declarações de vetores:
var
 nota: array [1..10] of real;
 nr_letras: array ['a'..'j'] of integer;
 caract: array [-4..7] of char;
Nesses exemplos, o vetor nota tem 10 elementos reais, com índices iniciando em 1 e crescen-
do até 10; o vetor nr_letras tem elementos inteiros, com índices do tipo caractere, tendo 
o primeiro elemento o índice “a” e o último o índice “j”; e o vetor caract, de elementos do 
tipo caractere, tem 12 elementos, tendo o primeiro o índice -4 e o último, 7. A Figura 6.8 
ilustra estes três vetores, simulando alguns valores contidos em seus elementos.
Quando os índices forem do tipo inteiro, recomenda-se que a declaração dos limites do 
vetor seja feita usando constantes previamente definidas. As duas declarações a seguir são 
equivalentes à declaração do vetor nota:
const LIMSUP = 10;
 LIMINF = 1;
var nota: array [LIMINF..LIMSUP] of real;
Nesse caso, todas as referências ao primeiro e último elemento do vetor ao longo do progra-
ma serão feitas utilizando as constantes declaradas. Dessa forma, o tamanho do vetor poderá 
Edelweiss_06.indd 183Edelweiss_06.indd 183 12/03/14 09:0212/03/14 09:02
Capítulo 15 Recursividade 427
A Figura 15.3 ilustra as chamadas recursivas realizadas para calcular o quinto termo dessa 
série.
exercício 15.3 Classificação de vetor pelo método Quicksort. No Capítulo 6 (Seção 
6.3.3), foi ressaltado que a classificação de um vetor é uma operação muito usual em apli-
cações e que há vários métodos disponíveis para realizá-la. Aqui, é apresentado um dos mé-
todos mais eficientes para classificar um vetor, denominado Quicksort ou ordenação rápida. 
Embora possa ser implementado somente por meio de comandos iterativos, a utilização de 
chamadas recursivas é recomendável, uma vez que a eficiência do método garante que o 
número de chamadas nunca seja elevado.
O método inicia buscando a posição correta do primeiro elemento do vetor (aqui chamado de 
pivô) e trocando-o para essa posição. Além de posicionar o pivô em seu lugar correto, todos 
os elementos antes dele serão menores do que ele e todos os posteriores, maiores do que ele. 
Isso é feito da seguinte maneira: o pivô é comparado com o segundo elemento, depois com 
o terceiro, etc., até que seja encontrado um (aqui nomeado de índice i) que seja maior do 
que ele. Em seguida, o pivô é comparado com o último elemento do vetor, depois com o pe-
núltimo, etc., até que seja encontrado um que seja menor do que ele (índice j). Os elementos 
de índices i e j são então permutados. Feita a troca, novamente o pivô é comparado com os 
elementos que seguem o elemento que estava em i, até que seja encontrado outro maior do 
que ele, depois com os elementos abaixo do j, até que seja encontrado outro menor do que 
ele, e nova permuta é feita. Esse processo é repetido até que i seja maior do que j, o que de-
fine o valor de j como a posição correta do pivô, que é então trocado com o elemento dessa 
posição. Uma vez posicionado o pivô, o vetor original está particionado em dois – no subvetor 
inferior, todos os elementos são menores do que o pivô e, no superior, todos são maiores. 
O mesmo método de ordenação é então repetido para cada um desses subvetores por meio 
de chamadas recursivas, passando, como parâmetros, os índices que limitam os subvetores.
Exemplificando, suponha um vetor de 9 elementos, numerados de 1 a 9, preenchido com os 
seguintes valores:
70 27 21 90 81 24 30 80 88
FIB (5)
FIB (3) + FIB (2)
FIB (2) + FIB (1)
FIB (2) + FIB (1)
FIB (4) + FIB (3)
figura 15.3 Chamadas recursivas para cálculo do quinto termo da série de Fibonacci.
Edelweiss_15.indd 427Edelweiss_15.indd 427 12/03/14 09:0012/03/14 09:00
428 Algoritmos e Programação com Exemplos em Pascal e C
A Figura 15.4 mostra resumidamente a sequência de valores no vetor durante a execução do 
método. Os índices i e j são utilizados para percorrer o vetor, o primeiro crescendo e o se-
gundo diminuindo. O pivô é o primeiro elemento, com valor 70. Quando i=4 e j=30, é feita a 
primeira permuta de valores, entre 90 e 30. A permuta seguinte acontece quando i=5 e j=6, 
sendo trocados de posição os valores 81 e 24. Quando i=6 e j=5, significa que foi encontra-
da a posição do pivô (posição 5), que é então permutado com o elemento dessa posição. Na 
figura, pode ser observado que agora todos os valores à esquerda de 70 são menores do que 
esse valor e todos os à direita dele são superiores a 70. Duas chamadas recursivas solicitam a 
ordenação do subvetor inferior, fornecendo os índices 1 e 4 como seus limites, e do subvetor 
superior, com índices limites 6 e 9. Na figura podem ser observados os valores decorrentes das 
permutas durantes as chamadas recursivas.
O procedimento a seguir implementa a classificação pelo método Quicksort. O procedimento 
utiliza o vetor V, do tipo TipoVetorInteiros, com valores inteiros, e um outro procedi-
mento, chamado troca, que permuta os conteúdos (valores inteiros) entre duas posições de 
memória recebidas como parâmetros.
Procedimento Quick
{CLASSIFICA O VETOR V EM ORDEM CRESCENTE, PELO MÉTODO QUICKSORT}
 Parâmetros de entrada:
 ref V (TipoVetorInteiros) {VETOR OU SUBVETOR A SER CLASSIFICADO}
 li, ls (inteiro) {LIMITES INFERIOR E SUPERIOR DOS ÍNDICES}
 Variáveis locais:
 i, j (inteiro) {ÍNDICES UTILIZADOS PARA PERCORRER O VETOR}
 pivô (inteiro) {VALOR CONTIDO NO PRIMEIRO ELEMENTO CONSIDERADO}
 sinal (lógico) {INDICA FINAL DE UMA VARREDURA}
início
24 27 21 30 70 81 90 80 88
Quick (V, 1, 4) Quick (V, 6, 9) 
24 27 21 30 81 90 80 88
24 21 27 30 81 80 90 88
21 24 27 30 80 81 90 88
21 27 30 80 88 90
i
70 27 21 90 81 24 30 80 88
70 27 21 30 81 24 90 80 88
70 27 21 30 24 81 90 80 88
j
j
i
i j
ij
figura 15.4 Simulação de valores no Quicksort.
Edelweiss_15.indd 428Edelweiss_15.indd 428 12/03/14 09:0012/03/14 09:00
Capítulo 15 Recursividade 429
 sinal ← falso {INICIALIZAÇÃO}
 se li < ls
 então início
 i ← li {POSICIONA I E J NO INÍCIO E NO FINAL}
 j ← ls + 1
 pivô ← v[li]
 repita
 i ← i + 1
 {AVANÇA I ENQUANTO O ELEMENTO FOR INFERIOR AO PIVÔ
 E NÃO CHEGAR AO FINAL DO SEGMENTO ANALISADO}
 enquanto (v[i]<pivô) e (i<ls)
 faça i ← i + 1
 j ← j – 1
 {RECUA J ENQUANTO O ELEMENTO FOR SUPERIOR AO PIVÔ
 E NÃO CHEGAR AO INÍCIO DO SEGMENTO ANALISADO}
 enquanto (v[j]>pivô) e (j>li)
 faça j ← j – 1
 se i < j {PERMUTA DOIS ELEMENTOS}
 então executar troca(v[i], v[j])
 senão sinal ← verdadeiro {INDICA QUE TERMINOU}
 até sinal
 executar troca(v[j], v[li]) {POSICIONA PIVÔ EM SUA POSIÇÃO}
 executar Quick(v, li, j-1)
 executar Quick(v, j+1, ls)
 fim
fim {Quick}
exercício 15.4 Pesquisa binária recursiva. No Exercício de Fixação 6.7 (no Capítulo 6), 
foi visto o método de pesquisa conhecido como pesquisa binária. Relembrando, esse méto-
do realiza a busca de um valor sobre um vetor já ordenado, comparando o valor buscado 
com o elemento que está na posição central do vetor. Se o valor não for encontrado nessa 
posição, a pesquisa segue buscando o valor na metade superior (caso o valor buscado seja 
superior ao valor que está no meio) ou na metade inferior(caso seja inferior ao valor do 
meio). Claramente, esse método pode ser implementado por meio de recursividade, pois a 
pesquisa na metade superior ou inferior é feita novamente da mesma maneira, alterando 
somente o tamanho do vetor analisado, ou seja, fazendo a chamada recursiva para a metade 
superior ou para a inferior.
A função a seguir realiza a pesquisa binária utilizando chamadas recursivas. Além do nome 
do vetor e do valor a ser pesquisado, são passados como parâmetros os índices que limitam o 
espaço do vetor a ser pesquisado. A função devolve o índice do elemento em que foi encon-
trado o valor buscado ou, no caso de não encontrá-lo, o valor -1 (supondo que esse índice 
não seja utilizado no vetor original).
Edelweiss_15.indd 429Edelweiss_15.indd 429 12/03/14 09:0012/03/14 09:00
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.
 
DICA DO PROFESSOR
Compreender o funcionamento e algumas soluções de implementação de métodos de ordenação, 
assim como melhorar os algoritmos de ordenação, é muito importante, para assim poder 
selecionar o que mais bem se aplica na solução do problema e otimizar as soluções já existentes, 
aumentando a sua eficiência. Assista ao vídeo para conhecer um pouco mais sobre esses 
métodos.
Conteúdo interativo disponível na plataforma de ensino!
 
EXERCÍCIOS
Várias são as derivações do método bolha como: ordenar em ordem crescente, decrescente, 
da direta para esquerda, da esquerda para a direita do vetor, formas mais simples e outras 
mais complexas. A empresa Tabajara Comunicações precisa de auxílio para ordenar os 150 
ramais telefônicos de sua empresa. Para simplificar o problema, realize o teste de mesa 
para as duas opções propostas para a ordenação do vetor ramais, considerando para o teste 
de mesa a quantidade de ramais como sendo a variável maximo =5 e não como 150, e o 
vetor ramais = {6,3,9,2,4}. O vetor ramais foi considerado como variável global em função 
do Visualg não passar vetor como referência, por isto ele não foi passado para a função 
ORDENA, somente a variável maximo, que representa o tamanho do vetor.
1) 
Com relação as duas propostas apresentadas para o método bolha, assinale a alternativa 
INCORRETA.
A) Na Opção I, o método bolha ordena os ramais na forma crescente e realiza a pesquisa da 
direita para a esquerda e vai colocando em ordem no início do vetor os menores elementos.
B) Na Opção II, o método bolha ordena os ramais na forma crescente e realiza a pesquisa da 
esquerda para a direita e vai colocando em ordem no final do vetor os maiores elementos.
C) As Opções I e II utilizam o método bolha onde ordena os ramais na ordem crescente 
dentro do vetor.
D) As Opções I e II utilizam o conceito da bolha, em que os valores maiores (mais pesados) 
vão para baixo (fim do vetor), e os valores menores (mais leves) flutuam para cima (para o 
início do vetor).
E) Nenhuma das alternativas está correta.
Um professor de uma universidade possui uma turma de 25 alunos na disciplina de 2) 
Física I e necessita, para análise, de um relatório de todas as notas dos alunos em 
ordem crescente. Sabendo-se que a nota para aprovação da disciplina é 7.0, o 
professor deseja saber quantos destes alunos tiveram aprovação e quantos tiveram 
reprovação na disciplina de Física I. Analise a proposta de implementação de 
ordenação das notas apresentada a seguir. 
// O vetor Notas é uma variável global no problema a seguir.
algoritmo "Ordena_notas"
var
notas: vetor[1..26] de inteiro
 
// Módulo para efetuar o cadastro de notas dos 25 alunos
procedimento ler_notas(num:inteiro)
var
indice:inteiro
inicio
escreval("*** DIGITE AS NOTAS DOS ALUNOS DE FÍSICA I PARA SEREM 
ORDENADOS ***")
para indice de 2 ate num passo 1 faca
 escreva("Nota do aluno (",indice-1,"): ")
 leia(notas[indice])
fimpara
fimprocedimento
 
// módulo que ordena as notas dos alunos
procedimento ordena_notas (num:inteiro)
var
h, indice: inteiro
sentinela: inteiro
inicio
indice <- 3
enquanto ( indice <=num)faca
 sentinela <- notas[indice]
 h <- indice -1
 notas[1] <- sentinela
 enquanto (sentinela < notas[h]) faca
 notas[h+1] <- notas[h]
 h <- h-1
 fimenquanto
 notas[h+1]<- sentinela
 indice <- indice+1
fimenquanto
fimprocedimento
 
// Módulo para efetuar o cálculo de quantos aprovaram e quantos reprovaram
procedimento calculo_notas(num:inteiro)
var
indice,totrep,totapr:inteiro
inicio
totrep <-0
totapr<-0
para indice de 2 ate num passo 1 faca
 se (notas[indice] <7) entao
 totrep <- totrep +1
 senao
 totapr <- totapr +1
 fimse
fimpara
escreval("")
escreval("***Total alunos aprovados em Física I : ", totapr)
escreval("***Total alunos reprovados em Física I: ", totrep)
fimprocedimento
 
// Módulo para efetuar a impressão das notas ordenadas
procedimento imprime_notas(num:inteiro)
var
indice:inteiro
inicio
escreval("")
escreval("***Relatório das notas dos alunos de Física I - Ordenados*** ")
para indice de 2 ate num passo 1 faca
 escreval("Notas ordenados(" , indice-1,"):",notas[indice])
fimpara
fimprocedimento
 
//corpo principal do algoritmo
inicio
ler_notas(26) //chama o módulo ler_codigos
ordena_notas(26) //chama o módulo ordena_codigos
imprime_notas(26) //chama o módulo imprime_codigos
calculo_notas(26)
fimalgoritmo
Selecione a alternativa que representa o método de ordenação utilizado para ordenar 
as notas na proposta de implementação descrita anteriormente.
A) Método bolha
B) Método de seleção
C) Método de inserção
D) Método QuickSort
E) Método ShellSort
Os métodos de ordenação de dados, cada um com suas peculiaridades, possuem um 3) 
objetivo simples e único: ordenar os dados de uma estrutura de dados. Em relação 
aos algoritmos de ordenação de dados, classifique como verdadeiras (V) ou falsas (F) 
cada uma das afirmativas abaixo e, a seguir, selecione a resposta com a sequência 
correta. 
I - O algoritmo de ordenação por intercalação (Merge sort) é o algoritmo que possui 
o melhor desempenho e, por isso, ordena os dados de forma mais rápida. 
II - O algoritmo de ordenação por bolha é o mais simples de ser implementado e, por 
isso, possui em sua estrutura quatro laços de repetição do tipo for.
III - O algoritmo de ordenação Quick sort é o mais eficiente entre todos os 
algoritmos, uma vez que ele necessita de menos iterações para ordenar a estrutura de 
dados.
IV - O algoritmo de ordenação por seleção tem esse nome porque seleciona um 
elemento da estrutura e percorre todo o vetor até o final, verificando se algum valor 
no vetor é maior que o valor selecionado. 
A) V - F - V - F
B) F - V - F - V
C) F - F - V - V
D) V - V - F - V
E) F - F - F - F
Os métodos simples de ordenação direta estudados na unidade de aprendizagem são mais 
utilizados para ordenar pequenos volumes de dados. Avalie as três alternativas de 
propostas de implementação de ordenação dos métodos de ordenação bolha, método por 
inserção e método por seleção. 
4) 
 
Levando-se em consideração que a entrada de dados possui valores iguais em todas as 
posições e o vetor denominado Elementos é de tamanho max=4. Qual dos métodos de 
ordenação apresentados realiza menos comparações entre os valores do vetor no processo 
de ordenação do vetor Elementos? 
A) O Método bolha realiza menos comparações para a ordenação dos elementos.
B) O método de seleção realiza menos comparações para a ordenação dos elementos.
C) Os métodos bolha e seleção possuem o mesmo número de comparações e realizam menos 
comparações do que o método de inserção.
D) O método de inserção realiza menos comparações para a ordenação dos elementos.
E) Os três métodos possuem o mesmo número de comparações para a ordenação dos 
elementos.
Analise o simulado do método de ordenação de um vetor de sete elementos inteiros 
apresentado na imagem a seguir. 
5) 
 
Baseado no funcionamentodo método apresentado, selecione a alternativa INCORRETA. 
A) O simulado de ordenação representa o método QuickSort.
B) O simulado apresenta a ordenação dos elementos menores do que o pivô à esquerda e os 
elementos maiores à direita do pivô.
C) A simulação utiliza a técnica da divisão do vetor.
D) O elemento pivô utilizado é o primeiro elemento do vetor.
E) O elemento pivô utilizado é o elemento central, calculado pelo valor inteiro da divisão da 
soma da primeira posição com a última posição do vetor.
NA PRÁTICA
A ordenação é uma técnica muito utilizada em muitos sistemas, sempre que se faz necessário 
classificar os elementos de alguma forma, como crescente ou decrescente, classificados ou 
agrupados por meio de uma determinada ordem e chave.
 
Como aplicação da ordenação em um sistema de produção, é possível citar:
- Relatório de produção diária por ordem de código de produto, ou sua descrição.
- Relatório de produção diária/mensal por máquina/operador.
- Relatório de compra de materiais por descrição do produto e sua quantidade.
- Relatório de estoque mínimo diário, ordenado por descrição do produto.
- Relatório de vendas por descrição de produtos (por região, país, cidade, etc.).
- Relatório de comissão de vendedores por nome, por mês, por dia, etc.
- Relatório de peças retrabalhadas e/ou desperdícios, por ordem de código ou descrição do 
produto e, ainda, pode-se exigir por dia, semana, mês ou ano.
- Entre outros.
Em uma construtora, para gerenciar o material e a mão de obra:
- Relatório de produtos consumidos em uma determinada ordem de uma obra, por dia, por 
descrição do produto, por mês, etc.
- Relatório de funcionários em uma determinada obra, em ordem alfabética por nome de 
funcionário ou por cargo, etc.
- Relatório de valores gastos de um determinado produto, em ordem de data de compra.
- Relação do total de horas a serem pagas aos funcionários de uma determinada obra (semanal 
ou mensal), em ordem alfabética de nome de funcionário.
- Entre outros.
SAIBA +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do 
professor:
Vídeo com o método insertion sort (inserção) : teoria , algoritmo em português e 
funcionalidade.
Conteúdo interativo disponível na plataforma de ensino!