Ordenação de dados

Ordenação de Dados
Muitas vezes é necessária a ordenação dos dados em uma estrutura (vetores, listas ligadas ou arquivos). Dependendo da forma como os dados estão armazenados, métodos de ordenação específicos são mais indicados. A ordem da ordenação acontece segundo uma chave (normalmente um campo dos dados contidos na lista). A ordenação pode ser crescente ou decrescente. Dados (records) Chave

Lista

Categorias de algoritmos de ordenação:
Troca - os algoritmos de troca utilizam a troca de posições dos dados: • Bolha – troca simples • Shakesort – troca alternada Inserção - os algoritmos de inserção removem, deslocam e inserem elementos da estrutura: • Direta • Shellsort Seleção - a ordenação por seleção isola um elemento posicionando-o na sua posição ordenada: • Direta • Heapsort - árvore Intercalação - a ordenação por intercalação utiliza a idéia de particionar em blocos a estrutura intercalando esses blocos: • MergeSort Partição ou Segmentação - a ordenação por partição baseia-se na subdivisão da lista em listas cada vez menores: • Quicksort

Algoritmos:
Implementações de alguns tipos de algoritmos de ordenação são apresentados nessa seção. As declarações necessárias para os testes das rotinas de ordenação estão após as implementações.

Troca
Esses algoritmos comparam dois a dois elementos vizinhos na lista e se a ordem não estiver correta os elementos são trocados.
#define MELHORADO #define VISUAL #ifndef MELHORADO void bolha(TVet v, int n) { int i, j; Dado x; for (i=1; i0; j--) if (v[j-1].chave > v[j].chave) { x=v[j-1]; v[j-1]=v[j]; v[j]=x; } #ifdef VISUAL mostraDados(v, n); #endif } } #else

void bolha(TVet v, int n) { int i, j; Dado x; bool ordenado; i=1; ordenado=false; while (!ordenado && i=i; j--) if (v[j-1].chave > v[j].chave) { x=v[j-1]; v[j-1]=v[j]; v[j]=x; ordenado=false; } #ifdef VISUAL mostraDados(v, n); #endif i++; } } #endif

Inserção
Método direto - dado uma lista para ordenação, percorrer elemento por elemento deslocando os