Estruturas de Dados - Ordenação Métodos Elementares

Prévia do material em texto

Ordenação Métodos Elementares
Estruturas de Dados
Profa. Carla Koike
   
Ordenação
● Ordenar
– processo de rearranjar um conjunto de objetos em 
uma ordem ascendente ou descendente.
● A ordenação visa facilitar a recuperação 
posterior de itens do conjunto ordenado.
– Dificuldade de se utilizar um catálogo telefônico se 
os nomes das pessoas não estivessem listados em 
ordem alfabética.
   
Notação
● Os algoritmos trabalham sobre registros ou 
estruturas de um arquivo.
● Cada registro possui uma chave utilizada para 
controlar a ordenação.
– Matrícula, id, código, etc...
● Podem existir outros componentes em um 
registro.
   
Chave de Ordenação
typedef long ChaveTipo;
typedef struct Item {
 ChaveTipo Chave;
 /* outros componentes */
} Item;
● Qualquer tipo de chave sobre o qual exista uma 
regra de ordenação bem­definida pode ser 
utilizado
   
Métodos Estáveis
● Um método de ordenação é estável se a ordem 
relativa dos itens com chaves iguais não se 
altera durante a ordenação.
●   Alguns dos métodos de ordenação mais 
eficientes não são estáveis.
● A estabilidade pode ser forçada quando o 
método é não­estável:
– Sedgewick (1988) sugere agregar um pequeno 
índice a cada chave antes de ordenar, ou então 
aumentar a chave de alguma outra forma.
   
Classificação dos Métodos
● Métodos Elementares
– Ordenação por Borbulhamento
– Ordenação por Inserção
– Ordenação por Seleção
● Métodos Eficientes
– Ordenação Quicksort
– Ordenação Shell
– Ordenação Heap
– Ordenação Mergesort
   
Métodos Elementares
● Adequados para pequenos arquivos.
● Requerem O(n2 ) comparações.
● Produzem programas pequenos.
   
Métodos Eficientes
●  Adequados para arquivos maiores.
●  Requerem O(n log n) comparações.
●  Usam menos comparações.
●  As comparações são mais complexas nos 
detalhes.
● Métodos simples são mais eficientes para 
pequenos arquivos.
   
Método da bolha ­ Bubblesort
● Processo básico:
– quando dois elementos estão fora de ordem, troque­os de 
posição
– até que o i­ésimo elemento de maior valor do vetor seja 
levado para as posições finais do vetor
– continue o processo até que todo o vetor esteja ordenado
   
Método da Bolha
void Bolha(char *item, int count)
{
    int a, b;
    char t;
    for( a = 1; a < count; ++a )
        for( b = count ­ 1; b > a; ­­b ) {
            if( item[ b — 1 ] > item[ b ] ) {
                t = item[ b ­ 1 ];
                item[ b — 1 ]= item[ b ];
                item[ b ] = t;
            }
        }
    }
}
   
Bolha – Implementação Melhorada
void bolha (int n, int* v)
{ int i, fim;                        
   for (fim=n­1; fim>0; fim­­) {      
        int troca = 0;
        for (i=0; i<fim; i++)
            if (v[i]>v[i+1]) {
                   int temp = v[i]; /* troca */
                   v[i] = v[i+1];
                   v[i+1] = temp;
                   troca = 1;
         }
      if (troca == 0) return; /* não houve troca */
   }
}
Pára quando há uma passagem inteira sem trocas
   
Método da Bolha: Complexidade
● Número de Comparações: n2/2 
● Complexidade Quadrática: O(n2)
   
Método de Seleção
●   Algoritmo:
– Selecione o menor item do vetor.
– Troque­o com o item da primeira posição do vetor.
– Repita essas duas operações com os n − 1 itens 
restantes, depois com os n − 2 itens, até que reste 
apenas um elemento.
   
Método de Seleção
   
Método de Seleção
void selectionSort(int vetor[],int tam)
{
 int i,j;
 int min,aux;
 for (i=0;i<tam­1;i++)
 {
   min=i;
   for (j=i+1;j<tam;j++)
   {
     if (vetor[j]<vetor[min])
       min=j;
   }
   aux=vetor[i];
   vetor[i]=vetor[min];
   vetor[min]=aux;
 }
}
   
Método de Seleção: Complexidade
● Número de Comparações C e Número de 
movimentações M:
   
Método de 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.
– É muito interessante para arquivos pequenos.
● Desvantagens:
– O fato de o arquivo já estar ordenado não ajuda em 
nada, pois o custo continua quadrático.
– O algoritmo não é estável
   
Método de Inserção
● Em cada passo a partir de i=2 faça:
– Selecione o i­ésimo item da seqüência fonte.
– Coloque­o no lugar apropriado na seqüência 
destino de acordo com o critério de ordenação.
   
Método de Inserção
●  A idéia de funcionamento é semelhante ao 
ordenamento de cartas de baralho na mão de 
um jogador. 
● O vetor a ser ordenado é dividido em dois 
segmentos: 
– o primeiro com os elementos já ordenado e o 
seguinte com o restante dos elementos ainda não 
ordenados. 
   
Método de Inserção
 void Insercao(Item *A, Indice *n)
{ Indice i, j;
  Item x;
  for (i = 2; i <= *n; i++) 
    { x = A[i];
      j = i ­ 1;
      A[0] = x;   /* sentinela */
      while (x.Chave < A[j].Chave) 
        { A[j+1] = A[j];
          j­­;
        }
      A[j+1] = x;
    } 
}
   
Método de Inserção ­ Complexidade
   
Método de Inserção
● O número mínimo de comparações e movimentos ocorre 
quando os itens estão originalmente em ordem.
● O número máximo ocorre quando os itens estão 
originalmente na ordem reversa.
● É o método a ser utilizado quando o arquivo está “quase” 
ordenado. 
● É um bom método quando se deseja adicionar uns poucos 
itens a um arquivo ordenado, pois o custo é linear.
● O algoritmo de ordenação por inserção é estável.
   
Métodos Eficientes
   
Método Quicksort
● Proposto por Hoare em 1960 e publicado em1962.
● É o algoritmo de ordenação interna mais rápido que 
se conhece para uma ampla variedade de situações.
● Provavelmente é o mais utilizado.
● A idéia básica é dividir o problema de ordenar um 
conjunto com n itens em dois problemas menores.
● Os problemas menores são ordenados 
independentemente.
●  Os resultados são combinados para produzir a 
solução final.
   
Método Quicksort
● Escolha um elemento da lista, denominado pivô;
● Rearranje a lista de forma que todos os elementos 
anteriores ao pivô sejam menores ou iguais a ele, e 
todos os elementos posteriores ao pivô sejam maiores 
ou iguais a ele. Ao fim do processo o pivô estará em 
sua posição final. Essa operação é denominada 
partição;
● Recursivamente ordene a sublista dos elementos 
menores e a sublista dos elementos maiores;
   
Quicksort
● Algoritmo para o particionamento:
– Escolha arbitrariamente um pivô x.
– Percorra o vetor a partir da esquerda até que A[i] ≥ 
x.
– Percorra o vetor a partir da direita até que A[j] ≤ x.
– Troque A[i] com A[j].
– Continue este processo até os apontadores i e j se 
cruzarem.
● As partes esquerda e direita do vetor são então 
ordenadas com chamadas recursivas
   
   
Quicksort
void sort(int array[], int begin, int 
end) {
   if (end ­ begin > 0) {
      int pivot = array[begin];
      int l = begin + 1;
      int r = end;
      while(l < r) {
         if (array[l] <= pivot) {
            l++;
         } else {
            swap(array[l], array[r]); 
            r­­;
         }
      }
      if (array[l] > pivot) {
         l­­;
      }
      swap(array[begin], array[l]);
      sort(array, begin, l­1);
      sort(array, r, end);
   }
}
   
Quicksort
void sort(int array[], int begin, int 
end) {
   if (end ­ begin > 0) {
      int pivot = array[begin];
      int l = begin + 1;
      int r = end;
      while(l < r) {
         if (array[l] <= pivot) {
            l++;
         } else {
            swap(array[l], array[r]); 
            r­­;
         }
      }
      if (array[l] > pivot) {
         l­­;}
      swap(array[begin], array[l]);
      sort(array, begin, l­1);
      sort(array, r, end);
   }
}
Partição
   
Quicksort ­ Análise
● Pior caso: ocorre quando, sistematicamente, o 
pivô é escolhido como sendo um dos extremos 
de um arquivo já ordenado
– O(n2)
● Caso Médio: ocorre quando cada partição 
divide o arquivo em duas partes iguais.
– O(n logn)
   
Quicksort
● Vantagens:
– É extremamente eficiente para ordenar arquivos de dados.
– Necessita de apenas uma pequena pilha como memória 
auxiliar.
– Requer cerca de n log n comparações em média para 
ordenar n itens.
● Desvantagens:
– Tem um pior caso O(n2 ) comparações.
– Sua implementação é muito delicada e difícil: Um pequeno 
engano pode levar a efeitos inesperados para algumas 
entradas de dados.
– O método não é estável.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31