Ordenação de Dados: Conceitos e Métodos

Prévia do material em texto

OBJETIVOS DE INVENTAR O COMPUTADOR??
Ordenação (computação)
• O problema de procurar “pesquisar” alguma informação 
numa tabela ou num catálogo é muito comum:
1.Procurar o telefone de uma pessoa no catálogo;
2.Procurar o nº da conta de certo cliente;
3.Consultar um determinado saldo em um terminal automático.
• Ordenação é o ato de se colocar os elementos de uma 
seqüência de informações, ou dados, em uma ordem 
predefinida. 
• O termo técnico em inglês para ordenação é SORTING, cuja 
tradução literal é "classificação".
• Algumas ordens são facilmente definidas. Por exemplo: 
• a ordem numérica;
• a ordem alfabética;
• crescentes ou decrescentes;
O principal objetivo de se ordenar é facilitar a recuperação de 
informação.
•Contudo, existem ordens, especialmente de dados 
compostos, que podem ser não triviais de se estabelecer.
• Exemplo: nomes se forem iguais, deve-se estabelecer 
outros critérios para a perfeita ordenação.
• A ordenação de um vetor significa fazer com que os seus 
elementos estejam colocados de acordo com algum critério 
de ordenação.
• Entre os mais importantes, podemos citar bubble sort (ou 
ordenação por flutuação), heap sort (ou ordenação por 
heap), insertion sort (ou ordenação por inserção), merge 
sort (ou ordenação por mistura) e o quicksort.
•Os métodos de ordenação são classificados em dois 
grupos.
• Se o arquivo a ser ordenado cabe toda na memória 
principal, então o método de ordenação é chamado 
ordenação interna. Cabe em um array
• Se o arquivo a ser ordenado não cabe na memória principal 
e por isso for armazenado em fita ou disco então o método 
de ordenação é chamado ordenação externa.
Diferenças entre os métodos:
• Em um método de ordenação interna, qualquer registro 
pode ser imediatamente acessado.
• Em um método de ordenação externa, os registros são 
acessados seqüencialmente ou em grandes blocos.
_ A maioria dos métodos de ordenação é baseada em 
comparações das chaves.
_ Existem métodos de ordenação que utilizam o princípio da 
distribuição.
Exemplo de ordenação por distribuição:
Considere o problema de ordenar um baralho com 52 cartas 
na ordem:
A < 2 < 3 < _ _ _ < 10 < J < Q < K
e
 ◊ 
Algoritmo:
1. Distribuir as cartas abertas em treze montes: ases, dois, 
três, : : :, reis.
2. Colete os montes na ordem especificada.
3. Distribua novamente as cartas abertas em quatro montes: 
paus, ouros, copas e espadas.
4. Colete os montes na ordem especificada.
Ordenação Interna
• São métodos simples, mas considerados eficientes.
• Adequados para pequenos arquivos;
• Produzem programas pequenos e de fácil entendimento.
– Ordenação por Seleção ; Ordenação por Inserção
– Shellsort; – Quicksort; – Heapsort
Na escolha de um algoritmo de ordenação interna deve ser 
considerado o tempo gasto pela ordenação.
Sendo n o número registros no arquivo, as medidas de 
complexidade relevantes são:
1. Número de comparações C(n) entre chaves.
2. Número de movimentações M(n) de itens do arquivo.
O uso econômico da memória disponível é um requisito 
primordial na ordenação interna.
Ordenação por Seleção
Algoritmo:
1) Selecione o menor item do vetor.
2) Troque-o com o item da primeira posição 1 do vetor.
3) Repita essas duas operações com os n -1 itens 
restantes, depois com os n -2 itens, até que reste 
apenas um elemento.
A idéia básica do Método de Seleção é, a cada 
passagem pelo vetor, selecionar o menor elemento e 
colocar este elemento o mais a esquerda possível.
Para isto deve-se trocar as posições dos elementos do 
vetor.
1.Na primeira passagem troca-se o menor elemento 
com o que está na primeira posição,
2.Na segunda passagem troca-se o segundo menor 
elemento com o que está na segunda posição . 
Assim por diante...
Desse modo, na passagem i só se deve procurar o menor 
elemento a partir do i-ésimo até o Nésimo elemento do 
vetor (os elementos anteriores já estarão ordenados).
Note-se que serão necessárias (N-1) passagens, pois, na 
última passagem, o N-ésimo elemento já estará na sua 
posição correta.
Vantagens:
1.Custo linear no tamanho da entrada para o 
número de movimentos de registros.
2.É o algoritmo a ser utilizado para arquivos com 
registros muito grandes.
3.É muito interessante para arquivos pequenos.
Desvantagens:
1. O fato de o arquivo já estar ordenado não ajuda 
em nada, pois o custo continua quadrático.
2.O algoritmo não é estável.
ALGORITMO EM PORTUGOL
{Método da Seleção}
declarar
I, J {variáveis de controle},
N {tamanho do vetor},
AUX {variável auxiliar para a troca},
:inteiros
A {vetor a ser ordenado} vetor com no máximo 30 elementos 
inteiros
inicio
solicitar a entrada do tamanho do vetor, ler (N)
solicitar a entrada dos dados do vetor 
para I de 1 até N
faça ler A[I]
fim para
para I de 1 até N
faça escrever A[I]
fim para
para I de 1 até N-1 
para J de I+1 até N
se A[I] > A[J]
então início
AUX ← A[I]
A[I] ← A[J]
A[J] ← AUX
Fim
fim-se
fim para
fim para
para I de 1 até N
faça escrever A[I]
fim para
fim-programa
//A variável I controla o pivô.A variável J controla os 
elementos a frente do pivô
— Selectsort (int data[],int n) {
— int min,tmp,i,j,min_id;
— for (i=0; i<n-1; i++) {
— min = data[i];
— for (j=i+1; j<n; j++)
— if (data[j] < min) {
— min = data[j];
— min_id = j;
— }
— tmp = data[i];
— data[i] = data[min_id];
— data[min_id] = tmp;
— }
— }