Algoritmos de Ordenação
●
Problema: encontrar um número de telefone em
uma lista telefônica


●
simplificado pelo fato dos nomes estarem em ordem
alfabética
e se estivesse sem uma ordem?
Problema: busca de um livro em uma biblioteca

a cada livro é atribuída uma posição relativa a outros
e portanto pode ser recuperado em um tempo hábil
Algoritmos de Ordenação
Terminologia básica
 seqüência de n ítens ou elementos
(registros)
●

r[0], r[1], ……….r[n-1]
a chave a[i] está associada ao elemento r[i]
●
●
usualmente a chave é um campo do registro
os elementos estão classificados pela chave
se i < j então a[i] precede a[j]
Terminologia básica
●
●
●
a ordenação tem por objetivo rearrumar as chaves de
forma que obedeçam a uma regra (ex.: ordem
numérica ou alfabética)
se os elementos representam registros de um arquivo,
sendo representado por uma lista sequencial em
memória principal
 a ordenação é interna
se o arquivo estiver em memória secundária
 a ordenação é externa
Terminologia básica
●
●
a ordenação pode ser por : contiguidade
física, valor indireto de ordenação e
encadeamento
os algoritmos podem operar sobre o elemento
ou sobre uma tabela de ponteiros


registro é muito grande: ordenação indireta
os registros não são rearrumados e sim os índices

●
●
Contiguidade física:
Existe uma forte característica física no
processo de ordenação,
Os elementos de um registro são
movimentados de sua posição física
original para sua nova posição

●
●
●
Vetor indireto de ordenação:
Não há movimentação das entradas das
posições originais.
A classificação é realizada com o apoio
de um arquivo-índice.
É esse arquivo que contém
apontadores para os registros reais, os
quais são mantidos classificados

●
●
●
●
Encadeamento:
Também não há a movimentação dos
registros das posições originais.
A ordem desejada é conseguida pelo
uso de uma lista ligada.
Coloca-se um campo a mais na tabela
para permitir que o próximo registro seja
identificado.
É necessário utilizar um ponteiro para o
primeiro elemento da lista ligada
Principais Métodos de
Ordenação Interna
●
Ordenação por inserção:


●
Ordenação por troca


●
Inserção direta
Incrementos decrescentes (shell sort)
Método da bolha ( buble sort)
Método da troca e partição ( quicksort)
Ordenação por seleção


Seleção direta
Seleção em árvore (heapsort)
Método da bolha - Bubble Sort
●
●
●
Em cada passo cada elemento é comparado
com o próximo
Se o elemento estiver fora de ordem a troca é
realizada
Realizam-se tantos passos quantos forem
necessários até que não ocorram mais trocas
Bubble Sort
2 6 3 5 7 9
2 6 3 5 7 9
2 3 6 5 7 9
2 3 5 6 7 9
2 3 5 6 7 9
Bubble Sort
2 3 5 6 7 9
2 3 5 6 7 9
2 3 5 6 7 9
●
Não ocorreram trocas
Bubble Sort
BUBBLESORT (V[], n)
houveTroca = verdadeiro
enquanto houveTroca for verdadeiro faça
houveTroca = falso
para i de 1 até n-1 faça
se V[i] > V[i + 1]
então troque V[i] e V[i + 1] de lugar e
houveTroca = verdadeiro
void bubble(int v[], int qtd)
{
int i, aux;
int trocou;
trocou = 1;
while (trocou)
{
qtd--;
trocou = 0;
for(i = 0; i < qtd; i++)
if(v[i] > v[i + 1])
{
aux=v[i];
v[i]=v[i+1];
v[i+1]=aux;
trocou = 1;
}
}
}
Ordenação por Seleção
●
Um dos algoritmos de classificação mais
simples:



ache primeiro o menor elemento da lista e
troque sua posição com o primeiro elemento
ache o segundo menor elemento e troque
sua posição com o segundo elemento
continue até que toda lista esteja ordenada
●
para cada i de 0 a n-2, troca o menor elemento
da sub-lista que vai de i a N-1 com a[i]
Ordenação por Seleção
inicial
9 2 6 3 5 7
2 9 6 3 5 7
2 3 6 9 5 7
Cada passo
acha o menor
e o coloca em
sua posição
2 3 5 9 6 7
2 3 5 6 9 7
2 3 5 6 7 9
void selectionSort(int vetor[],int tam)
{
int i,j;
int min,aux;
for (i=0;i<tam-2;i++)
{
min=i;
for (j=i+1;j<tam-1;j++)
{
if (vetor[j]<vetor[min])
min=j;
}
aux=vetor[i];
vetor[i]=vetor[min];
vetor[min]=aux;
}
}
Ordenação por Inserção Direta
●
●
●
Um primeiro elemento está no vetor ordenado
e os demais no vetor desordenado
Retira-se o primeiro elemento do vetor
desordenado. Ao colocá-lo no vetor ordenado,
é realizada a devida comparação para inserilo na sua posição correta
Repete-se o processo até que todos os
elementos do vetor desordenado tenham
passado para o vetor ordenado
Inserção Direta
6| 3
3 6|
3 4
3 4
3 4
3 4
4
4
6|
5
5
5
59 8
59 8
5 98
6|98
69|8
6 8 9|
Inserção Direta
InsertionSort(V, n)
for j← 2 to n do
aux ← V[j]
► insere V[j] na parte ordenada
V[1..j-1]
i←j–1
while i > 0 e V[i] > aux do
V[i + 1] ← V[i]
i←i–1
V[i + 1] ← aux
void insertSort(int a[], int length)
{
int i, j, value;
for(i = 1; i < length; ++i)
{
value = a[i];
for (j = i - 1; j >= 0 && a[j] > value; --j)
a[j + 1] = a[j];
a[j+1] = value;
}
}