Ordenação

Páginas: 6 (1310 palavras) Publicado: 3 de fevereiro de 2014
Ordenação (Parte 1)
Prof. Túlio Toffolo
http://www.toffolo.com.br

BCC202 – Aula 13
Algoritmos e Estruturas de Dados I

Critério de Ordenação
•  Ordena-se de acordo com uma chave:
typedef int TChave;
typedef struct {
TChave Chave;
/* outros componentes */
} TItem;

2

Características
•  Estabilidade: relativo à manutenção da ordem original
de itens de chaves iguais
• Ordenação interna: dados a serem ordenados cabem
todos na memória principal.
•  Princípio: comparação x distribuição

3

Critério de Avaliação
•  Sendo n o número de registros no arquivo, as medidas
de complexidade relevantes são:
•  Número de comparações C(n) entre chaves.
•  Número de movimentações M(n) de itens

4

Outras Considerações
•  O uso econômico da memória disponível é umrequisito
primordial na ordenação interna.
•  Métodos de ordenação in situ são os preferidos.
•  Métodos in situ não utilizam memória adicional.

•  Métodos que utilizam listas encadeadas não são muito
utilizados.
•  Métodos que fazem cópias dos itens a serem ordenados
possuem menor importância.

5

Métodos
•  Métodos a que estudaremos hoje:
•  Bolha (BubbleSort)
•  Seleção(SelectSort)
•  Inserção (InsertSort)

6

ORDENAÇÃO DA BOLHA

BUBBLESORT

Método Bolha
•  Os elementos vão “borbulhando” a cada iteração do
método até a posição correta para ordenação da lista
•  O método poderia parar quando nenhum elemento
borbulhace/trocasse de posição
•  Como os elementos são trocados (borbulhados)
frequentemente, há um alto custo de troca de elementos

8

MétodoBolha
void Bolha (TItem* v, int n) {
int i, j;
TItem aux;
for (i = 0; i < n-1; i++) {
for (j = 1; j < n-i; j++) {
if (v[j].Chave < v[j-1].Chave) {
aux = v[j];
v[j] = v[j-1];
v[j-1] = aux;
}
}
}
}


9

Análise de Complexidade
•  Comparações – C(n)
n−2

n−2

n−2

i =0

C ( n) =

n−2

i =0

i =0

i =0

∑ (n − i − 1) = ∑ n − ∑ i − ∑1

(0 + n − 2)(n− 1)
= n(n − 1) −
− (n − 1)
2
2
n −n
=
= O(n 2 )
2
•  Movimentações – M(n)

M (n) = 3C(n) = O(n 2 )
10

Ordenação por Bolha
•  Vantagens:
•  Algoritmo simples
•  Algoritmo estável

•  Desvantagens:
•  O fato de o arquivo já estar ordenado não ajuda reduzir o
número de comparações (o custo continua quadrático),
porém o número de movimentação cai a zero.

•  Possívelmodificação na atual implementação?

11

Método Bolha
void Bolha (TItem* v, int n) {
int i, j;
TItem aux;
for (i = 0; i < n-1; i++) {
for (j = 1; j < n-i; j++) {
if (v[j].Chave < v[j-1].Chave) {
aux = v[j];
v[j] = v[j-1];
v[j-1] = aux;
}
}
}
}


12

Método Bolha – Melhoria!!!
void Bolha (TItem* v, int n) {
int i, j, troca;
TItem aux;
for (i = 0; i < n-1; i++){
troca = 0;
for (j = 1; j < n-i; j++) {
if (v[j].Chave < v[j-1].Chave) {
aux = v[j];
v[j] = v[j-1];
v[j-1] = aux;
troca++;
}
}
if (troca == 0) break;
}
}


13

ORDENAÇÃO POR SELEÇÃO

SELECTSORT

Método Seleção
•  Seleção do n-ésimo menor (ou maior) elemento da lista
•  Troca do n-ésimo menor (ou maior) elemento com a nésima posição da lista
•  Uma únicatroca por vez é realizada

15

Método Seleção
void Selecao (TItem* v, int n) {
int i, j, Min;
TItem aux;
for (i = 0; i < n - 1; i++) {
Min = i;
for (j = i + 1 ; j < n; j++)
if (v[j].Chave < v[Min].Chave)
Min = j;
aux = v[Min];
v[Min] = v[i];
v[i] = aux;
}
}

16

Análise de Complexidade
•  Comparações – C(n)
n−2

n−2

n−2

i =0

C ( n) =

n−2

i =0i =0

i =0

∑ (n − i − 1) = ∑ n − ∑ i − ∑1

(0 + n − 2)(n − 1)
= n(n − 1) −
− (n − 1)
2
n2 − n
=
= O(n 2 )
2

•  Movimentações – M(n)

M (n) = 3(n −1) = O(n)
17

Ordenação por Seleção
•  Vantagens:
•  Custo linear no tamanho da entrada para o número de
movimentos de registros.
•  É o algoritmo a ser utilizado para arquivos com registros
muito grandes (alto custo de...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Ordenação
  • Ordenação
  • Ordenação
  • Ordenação
  • Ordenação
  • Ordenação
  • ordenação
  • Ordenacao

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!