Aplicação de Ordenação de Dados

Prévia do material em texto

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) :
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.
a)
Interação 1 = 9 comparações
Interação 2 = 8 comparações
Interação 3 = 7 comparações
Interação 4 = 6 comparações
Interação 5 = 5 comparações
Interação 6 = 4 comparações
Interação 7 = 3 comparações
Interação 8 = 2 comparações
Interação 9 = 1 comparações
Total de comparações realizadas no algoritmo atual = (9+8+7+6+5+4+3+2+1) = 45 comparações
Total de trocas realizadas: 13 trocas
b)
Interação 1 = 9 comparações
Interação 2 = 8 comparações
Interação 3 = 7 comparações
Interação 4 = 6 comparações
Na interação 4 ele já não realiza nenhuma troca, assim termina o algoritmo e as comparações pois o vetor já está ordenado.
Total de comparações realizadas no algoritmo novo = (9+8+7+6) = 30 comparações
Total de trocas = 13 trocas
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.
Uma proposta do novo algoritmo implementado.
// desafio algoritmos da empresa Tabajara para ordenar códigos de funcionários
// o vetor codigos é uma variável global no problema abaixo.
algoritmo "OrdenaCodigos"
var
codigos: vetor[1..10] de inteiro
// Módulo para efetuar o cadastro dos códigos
procedimento ler_codigos(num:inteiro)
var
indice:inteiro
inicio
escreval("*** DIGITE OS CÓDIGOS DOS FUNCIONÁRIOS PARA SEREM ORDENADOS ***")
para indice de 1 ate num passo 1 faca
 escreva("Codigo Funcionário(",indice,"): ")
 leia(codigos[indice])
fimpara
fimprocedimento
// modulo que ordena(método bolha)
procedimento ordena_codigos (num:inteiro)
var
h, indice,auxiliar: inteiro
troca, total: inteiro
inicio
indice <- 1
troca <-0
enquanto ( indice <=num)ou (troca<>0) faca
 h <- num
 troca <- 0
 enquanto (h>indice) faca
  se(codigos[h] < codigos[h-1]) entao
   auxiliar <- codigos[h-1]
   codigos[h-1] <- codigos[h]
   codigos[h] <- auxiliar
   troca <- troca+1
   total <- total + 1
  fimse
  h <- h-1
 fimenquanto
 indice <- indice+1
fimenquanto
escreval("")
escreval("****** Total de trocas realizadas : ", total)
fimprocedimento
procedimento imprime_codigos(num:inteiro)
var
indice:inteiro
inicio
escreval("")
escreval("***Relatório dos Códigos dos funcionários Ordenados*** ")
para indice de 1 ate num passo 1 faca
 escreval("Códigos ordenados(" , indice,"):",codigos[indice])
fimpara
fimprocedimento
//corpo principal do algoritmo
inicio
ler_codigos(10) //chama o módulo ler_codigos
ordena_codigos(10) //chama o módulo ordena_codigos
imprime_codigos(10) //chama o módulo imprime_codigos
fimalgoritmo