Ordenação

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 é um requisito 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é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;
}
}
}
}

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 −