Ordenação radix, counting , buket

Classificação de Dados em Tempo Linear

Classificação e Pesquisa de Dados
Aula 10 Classificação em Tempo Linear O(n): Counting Sort, Radix Sort e Bucket Sort

Algoritmos de classificação em tempo linear exploram determinadas propriedades do conjunto de dados a ser ordenado

Principais Algoritmos n n n

Counting sort Radix sort Bucket sort
3

UFRGS

INF01124
1

Classificação de Dados em Tempo Linear
Heapsort e Merge Sort apresentam desempenho de Θ(nlog2n) Quicksort tem custo médio de O(nlog2n) Estes algoritmos se baseiam em comparações entre os valores de chaves a serem ordenados e, portanto, são algoritmos de classificação por comparação Todo algoritmo de classificação por comparação está limitado por Ω(nlog2n). Portanto, Heapsort e Merge sort são assintoticamente ótimos Existem algoritmos que apresentam custo linear (i.e., O(n))

Classificação de Dados por Distribuição de Chaves – Counting Sort
Princípio de classificação n Assume que cada um dos n elementos de entrada é um inteiro no intervalo de 1 a k Quando k = O(n), o algoritmo executa em um tempo O(n) Idéia básica: determinar para cada elemento x da entrada, o número de elementos menores que x Pequeno ajuste necessário para suportar valores de chaves repetidos Utiliza dois outros vetores auxiliares

n n

n n

O algoritmo é estável
2 4

1

Procedimento Counting Sort
Proc counting-sort (A, B, k) /* B: vetor que conterá a saída ordenada; k: tamanho do intervalo */ begin for i ← 1 to k /* inicializa acumuladores */ do C[i] ← 0; for i ← 1 to length[A] do C[A[i]] ← C[A[i]] + 1; for i ←2 to k do C[i] ← C[i] + C[i-1]; for j ← length[A] downto 1 do begin B[C[A[j]]] ← A[j]; C[A[j]] ← C[A[j]] - 1; end end /* Armazena A[i] em sua posição final */ /* Decrementa acum. p/ suportar chaves repetidas */ /* C[i] = numero de elementos iguais a i */ /* C[i] = numero de elementos menores ou iguais a i */

Counting Sort Exemplo (Cont.)
1 2 3 4 5 6 7 8 1 2 3 4 5 6

… for j ← length[A]