ORDENAÇÃO EM
TEMPO LINEAR
Ordenação em Tempo Linear
• Algoritmos de ordenação por comparação:
• InsertSort;
• Quicksort;
• MergeSort;
• Heapsort...
• Possuem limite assintótico inferior: O(n lg n);
• Podem existir algoritmos melhores?
Ordenação em Tempo Linear
• A resposta é SIM, desde que:
• A entrada possua características especiais;
• Algumas restrições sejam respeitadas;
• O algoritmo não seja puramente baseado em
comparações;
• A implementação seja feita da maneira adequada.
• Tempo linear: Θ(n);
• Algoritmos:
• Ordenação por contagem (Counting sort);
• Radix sort;
• Bucket sort.
ORDENAÇÃO POR
CONTAGEM
Counting Sort
COUNTING SORT
• Aspectos Positivos:
• Ordena vetores em tempo linear para o tamanho do
vetor inicial;
• Não realiza comparações;
• É um algoritmo de ordenação estável;
• Aspecto Negativo:
• Necessita de dois vetores adicionais para sua
execução, utilizando, assim, mais espaço na memória.
COUNTING SORT
• Funcionamento:
• A ordenação por contagem pressupõe que
cada um dos n elementos do vetor de entrada é
um inteiro entre 1 e k (k representa o maior
inteiro presente no vetor).
• A ideia básica é determinar, para cada
elemento de entrada x, o numero de elementos
menores ou iguais a x. Com essa informação é
possível determinar exatamente onde o
elemento x será inserido.
EXEMPLO
A=
5
1
9
2
0
7
2
8
9
5
2
3
4
5
6
7
8
9
7
B=
1
2
3
4
5
6
7
8
9
 Na lista A acima o elemento circulado 7
possui 5 elementos menores que ele. Dessa
forma o elemento 7 deverá ser inserido no
índice 6 (5 + 1) do vetor de saída B.
SIMULAÇÃO - COUNTING SORT
O algoritmo recebe um vetor desordenado como entrada:
1
A=
2
2
5
3
3
4
0
5
2
6
3
7
0
8
3
Em seguida, gera os vetores adicionais B e C:
1
2
3
4
5
6
7
8
B=
 O vetor B é do mesmo tamanho do vetor A (8 elementos).
0
1
2
3
4
5
C= 0 0 0 0 0 0
 O vetor C é do tamanho do maior elemento de A + 1 (5 + 1 = 6).
SIMULAÇÃO - COUNTING SORT
Se o valor de um elemento de entrada é i, incrementamos C[i]:
C=
0
1
2
3
4
5
2
0
2
3
0
1
C[i] contém um número de elementos de entrada igual a i para
cada i = 0,1,2,...,k.
Agora fazemos C[i] = C[i] + C[i-1] para determinarmos quantos
elementos de entrada são menores que ou iguais a i:
C=
0
1
2
3
4
5
2
2
4
7
7
8
SIMULAÇÃO - COUNTING SORT
Agora, partindo do maior para o menor índice, fazemos
B[C[A[j]]] = A[j]. Assim, colocamos cada elemento A[j] em sua
Posição ordenada no vetor B:
Exemplo:
Para j = 8
B[C[A[8]]]  B[C[3]]  B[7]
B[7] = A[8]  B[7] = 3
SIMULAÇÃO - COUNTING SORT
Em seguida decrementamos o valor de C[A[j]] toda vez que
Inserimos um valor no vetor B. isso faz com que o próximo
elemento de entrada com valor igual a A[j], se existir, vá para
a posição imediatamente anterior a A[j] no vetor B.
C=
0
1
2
3
4
5
2
2
4
7
7
8
C[3] = C[3] – 1:
C=
0
1
2
3
4
5
2
2
4
6
7
8
SIMULAÇÃO - COUNTING SORT
Após as iterações de (comprimento de [A] até 1) temos o vetor de
saída B ordenado!!!
B=
1
2
3
4
5
6
7
8
0
0
2
2
3
3
3
5
ALGORITMO
COUNTING SORT
01
02
03
04
05
06
07
08
09
10
11
CountingSort(A, B, k) {
for I0 to k
do C[i] 0
for j1 to comprimento [A]
do C[A[j]] C[A[j]] + 1
for I2 to k
do C[i] = C[i] + C[i-1]
for j comprimento [A] downto 1
do B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1
}
COUNTING SORT IN C
void coutingSort(int *A, int n, int *B, int *C, int k){
int i;
// Passo 1 - Contagem do número de cada elemento do intervalo
for(i=0; i<n; i++)
C[A[i]-1]++;
// Passo 2 - Soma os números da casa atual, com os números da casa anterior
for(i=1;i<k;i++)
C[i] += C[i-1];
// Passo 3 - Alocação dos valores no vetor ordenado
for(i=n-1;i>=0;i--) {
B[C[A[i]-1]-1] = A[i];
C[A[i]-1]--;
}
//Passo 4 - Passar o conteúdo do vetor final para o vetor original.
for(i=0;i<n;i++)
A[i] = B[i];
}
ORDENAÇÃO
RADIXSORT
INTRODUÇÃO
Radixsort
Exercícios
• Implementar os algoritmos RadixSort e CountSort
realizando experimentos que avaliem a quantidade de
operações (comparações) e o tempo de execução para:
• vetores com 1.000, 10.000, 100.000 e um milhão de
números inteiros entre 0 e 99.999. Os números inteiros
serão gerados aleatoriamente.