BASEADO NA APRESENTAÇÃO DE
Prof. Ronaldo S. Mello
INE5384 - Estruturas de Dados
UFSC-CTC-INE
Ordenação de Dados
em Memória
Ordenação de Dados
•
•
Processo bastante utilizado na computação
de uma estrutura de dados
Dados ordenados garantem uma melhor
performance de pesquisa a uma ED
– busca seqüencial
•
evita a varredura completa de uma lista de dados
– busca binária
•
•
só é possível se os dados estão ordenados
apresenta baixa complexidade
Compromisso
• “A complexidade da ordenação da ED
não deve exceder a complexidade da
computação a ser feita na ED sem o
processo de ordenação”
• Exemplo: deseja-se realizar uma única
pesquisa a um vetor
– busca seqüencial  O(n)
– ordenação  O(n log n)
– Não vale a pena ordenar!
Considerações
•
•
Dados estão mantidos em um vetor
Elemento do vetor
– objeto que possui um atributo chave que deve
ser mantido ordenado
•
•
Um método troca(x,y) realiza a troca dos
elementos presentes nas posições x e y do
vetor
Para fins de exemplo, números inteiros
serão utilizados como elementos
Métodos de Ordenação
• Ordenação por troca
– BubbleSort (método da bolha)
– QuickSort (método da troca e partição)
• Ordenação por inserção
– InsertionSort (método da inserção direta)
– BinaryInsertionSort (método da inserção direta binária)
• Ordenação por seleção
– SelectionSort (método da seleção direta)
– HeapSort (método da seleção em árvore)
• Outros métodos
– MergeSort (método da intercalação)
– BucketSort (método da distribuição de chave)
Métodos de Ordenação Simples
•
São três
– BubbleSort
– InsertionSort
– SelectionSort
•
Características
– fácil implementação
– alta complexidade
– comparações ocorrem sempre entre posições
adjacentes do vetor
“Revisão” de Somatória
• Propriedade 1 (P1)
n
i
=
n (n + 1)
i=1
2
• Propriedade 2 (P2)
n
ki
i=1
n
= k

i=1
i
SelectionSort
•
SelectionSort é um método simples de
seleção
– ordena através de sucessivas seleções do
elemento de menor valor em um segmento nãoordenado e seu posicionamento no final de um
segmento ordenado
troca
e2
e5
e8
...
e6
e2
e5
e6
...
e8
Ordenação por Seleção
• Característica particular
– realiza uma busca seqüencial pelo menor
valor no segmento não-ordenado a cada
iteração
• Simulação de funcionamento
http://math.hws.edu/TMCM/java/xSortLab
Seleção - Complexidade
• Para qualquer caso
troca
1a V: n-1 comparações
9
5
1
2
4
2a V: n-2 comparações
1
5
9
2
4
1
2
9
5
4
1
2
4
5
9
...
(n-1)a V: 1 comparação
n-1
i =
i=1
(n - 1) n
2

O(n2)
Seleção - Implementação
void Ordenação_por_Seleção(tipo vet[], int qtpos)
{
int fim, i, posmaior;
tipo aux;
fim=qtpos -1; /* inic todo vetor está desordenado */
while (fim>0) /* qdo fim=0,a parte desord tem1 elem , logo, está ordenado*/
{
posmaior=Escolhe_maior (vet,fim);
if (posmaior!= fim) /* se o maior já está na ultpos da parte desord. nada há
a fazer */
{
aux=vet[fim];
vet[fim]=vet[posmaior];
vet[posmaior]=aux,
}
fim - -;
}
}}
Seleção - Implementação
int Escolhe_maior(tipo v[], int upt)
{
/* Acessa cada posição da parte desordenada do vetor,procurando
onde está maior valor*/
int pM,i;
pM=0;
for(i=1;i<=up;i++)
{
if (v[i]>v[pM])
pM=i;
}
return ( pM)
}
Bolha
•
BubbleSort é um método simples de troca
– ordena através de sucessivas trocas entre
pares de elementos do vetor
•
Características
– realiza varreduras no vetor, trocando pares
adjacentes de elementos sempre que o próximo
elemento for menor que o anterior
– após uma varredura, o maior elemento está
corretamente posicionado no vetor e não
precisa mais ser comparado
•
após a i-ésima varredura, os i maiores elementos
estão ordenados
Bolha
• Simulação de funcionamento
http://math.hws.edu/TMCM/java/xSortLab
Bolha - Complexidade
• Para um vetor de n elementos, n – 1
varreduras são feitas para acertar todos
os elementos
início:
4
9
2
1
5
1a V: n – 1 comparações
4
2
1
5
9
2a V: n – 2 comparações
...
2
1
4
5
9
(n-2)a V: 2 comparações
1
2
4
5
9
(n-1)a V: 1 comparação
1
2
4
5
9
1
2
4
5
9
n=5
fim:
Bolha - Complexidade
• Definida pelo número de comparações
envolvendo a quantidade de dados do
vetor
• Número de comparações:
(n - 1) + (n – 2) + ... + 2 + 1
• Complexidade (para qualquer caso):
n-1
i =
i=1
(n - 1) n
2

O(n2)
Bolha - Implementação
void Bolha(tipo vet[], int qtpos)
{
int ultroca,fimdesord,ultroca;
tipo aux;
for(fimdesord=qtpos-1;fimdesord>0;fimdesord=ultroca)
{
ultroca=0;
for(i=0;i<fimdesord;i++)
/* ult. pos. que tem vizinho à direita é a penúltima*/
{
if(vet[i]>vet[i+1])
{
aux=vet[i];
vet[i]=vet[i+1];
vet[i+1]=aux;
ultroca=i; /* guarda onde realizou a última troca pois a
parte antecessora a esta posição no
vetor pode ter ficado desordenada */
}
}
}
Ordenação por Inserção
•
•
InsertionSort é um método simples de
inserção
Características do método de inserção
– considera dois segmentos (sub-vetores) no
vetor: ordenado (aumenta) e não-ordenado
(diminui)
– ordena através da inserção de um elemento por
vez (primeiro elemento) do segmento nãoordenado no segmento ordenado, na sua
posição correta
Método de Inserção
e5
e9
...
segmento ordenado
e5
•
e8
e8
e2
segmento não-ordenado
e9
...
e2
Inicialmente, o segmento ordenado
contém apenas o primeiro elemento do
vetor
InsertionSort
•
•
realiza uma busca seqüencial no segmento
ordenado para inserir corretamente um
elemento do segmento não-ordenado
nesta busca, realiza trocas entre elementos
adjacentes para ir acertando a posição do
elemento a ser inserido
e5
e9
e8
...
e2
e5
e8
e9
...
e2
InsertionSort
• Simulação de funcionamento
http://math.hws.edu/TMCM/java/xSortLab
InsertionSort - Complexidade
• Pior caso: vetor totalmente desordenado
9
5
4
2
1
1a V: 1 comparação
5
9
4
2
1
2a V: 2 comparações
...
4
5
9
2
1
(n-2)a V: n-2 comparações
2
4
5
9
1
(n-1)a V: n-1 comparações
1
2
4
5
9
n=5
início:
n-1
i =
i=1
(n - 1) n
2

O(n2)
InsertionSort - Complexidade
• Melhor caso: vetor já ordenado
1
2
4
5
9
1a V: 1 comparação
1
2
4
5
9
2a V: 1 comparação
...
1
2
4
5
9
(n-2)a V: 1 comparação
1
2
4
5
9
(n-1)a V: 1 comparação
1
2
4
5
9
n=5
início:
n - 1  O(n)
InsertionSort X BubbleSort
Melhor caso
InsertionSort
O(n)
BubbleSort
O(n2)
Pior caso
O(n2)
O(n2)
Comparação
Melhor caso
Pior caso
InsertionSort
O(n)
O(n2)
BubbleSort
O(n2)
O(n2)
SelectionSort
O(n2)
O(n2)
Exercícios
•
•
•
•
•
•
•
Faça um programa que gerencie uma agenda de telefones. O programa deve ser
capaz de armazenar as informações para até 100 pessoas. A agenda deve conter o
nome e o telefone de cada pessoa, devendo ser possível realizar as seguintes
operações: consulta de um telefone, inclusão de um novo telefone; alteração do
número de um telefone já cadastrado; exclusão de um telefone; impressão dos
telefones cadastrados; ordenação por nome; consulta a partir do nome de uma
pessoa; armazenamento dos dados em um arquivo(escreve_tudo) e recuperação dos
dados do arquivo (le_tudo). A rotina de consulta de um telefone obtido o nome,
quando o mesmo não está cadastrado deve perguntar ao usuário se o mesmo deve
ser incluído.
a) faça uma função chamada le_tudo() que pergunta o nome do arquivo que
contém a agenda. Se o mesmo existir, leia as informações do arquivo. A função
retorna a quantidade de registros lidos. Se o arquivo não existe, a função retorna 0
(zero). O nome perguntado deve ser mantido
b)
faça uma função chamada escreve_tudo() que escreva tudo no arquivo cujo
nome é o mesmo da rotina de leitura..
c) faça uma função para cada tarefa que o programa realiza.
Obs;O programa deverá avisar ao usuário sempre que não puder realizar as
alterações. Faça cada tarefa e teste- Comece pela le_tudo, a seguir faça a inclusão e
a escreve_tudo.
Não se esqueça de fazer a função main().