Métodos de ordenação

Métodos de Ordenação
Elementares
Algoritmos e Estuturas de Dados
Inverno 2006

Cátia Vaz

1

Contexto
Objectivo: estudar métodos de ordenação de qualquer tipo de dados.
Para a ordenação de um determinado tipo de dados, é associado a cada elemento uma chave que o caracteriza. exemplo: a ordem natural do tipo de dados

Interface Comparable
A classe que descreve o tipo de dados tem que implementar a interface Comparable para especificar uma ordem natural: o método compareTo especifica uma ordem total; exemplo de tipos comparáveis: String, Integer e Double para que os objectos de uma classe definida pelo utilizador sejam comparáveis, é necessário que a classe implemente a interface
Comparable.

Cátia Vaz

2

Operações Abstractas
As operações abstractas nos dados a utilizar são: a comparação (less); a troca (exch). static boolean less(int v, int w) { return v < w;} static void exch(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t;} static void compExch(int[] a, int i, int j) { if (less(a[i],a[j])) exch(a,i,j);}

Cátia Vaz

3

Definições
Tipos de algoritmos de ordenação: não adaptativos – sequência de operações independente da ordenação original dos dados; adaptativos – sequência de operações dependente do resultado de comparações.

Um algoritmo de ordenação é dito estável se preserva a ordem relativa dos elementos com chaves repetidas
Um algoritmo de ordenação é dito interno, se o conjunto de todos os dados a ordenar couber na memória; caso contrário é dito externo.
Cátia Vaz

4

Definições
Um algoritmo de ordenação é dito directo se os dados são acedidos directamente nas operações de comparação e troca; caso contrário é dito indirecto. Cátia Vaz

5

Selection Sort
Ideia do Algoritmo: procurar o menor elemento e trocar com o elemento na primeira posição procurar o segundo menor elemento e trocar com o elemento na segunda posição proceder assim até a ordenação estar completa