Algoritmos de Ordenação
1. Inserção
Princípio:
"Inserir" o i-ésimo elemento na posição "correta" do subvetor v[0 ... i - 1]
Ex.:
0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
3 | -1 | 7 | 2 | 4 |
void insertion(int *v, int n){
for(int i = 1; i < n; i++){
for (int j = i; j > 0 && v[j] < v[j-1]; j--)
{
troca(&v[j], &v[j-1]);
}
}
}
Complexidade \(O(n^2)\) e \(O(n)\) para um vetor já ordenado.
2. Seleção
Princípio:
"Selecionar" o elemento do subvetor v[i ... m - 1] e coloca na posição i.
Ex.:
0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
2 | 5 | 1 | 0 | 3 |
void selection(int *v, int n){
for(int i = 0; i < n, i++){
int menor = 1;
for(int j = i + 1; j < n; j++)
if(v[j] < v[menor]) menor = j;
troca(&v[i], &v[menor]);
}
}
3. Estabilidade
Dizemos que o algoritmo de ordenação é estável se, ao ordenar, ele preserva a ordem original elementos iguais.
Inserção é estável, mas a seleção não.
4. Ordenação por Intercalação
A intercalação consiste em unir dois conjuntos ordenados em um só. Em termos de vetores: Dado um vetor v[e ... d] tal que v[e ... m] e v[m+1 ... d] são subvetores ordenados, para \(e<=m<=d\), desejo qie v[0 .. n-1] fique ordenado.
void intercala(int *v, int e, int d){
int j = e, j = m, k = 0;
int *aux = malloc((d - e + 1) * sizeof(int));
while(i < m && j <= d){
if(v[i] <= v[j]){
aux[k] = v[i]; k++; j++;
} else {
aux[k] = v[j]; k++; j++;
}
}
while(i<m) aux[k++] = v[i++];
while(j<=d) aux[k++] = v[j++];
for(k = 0; i = e; i <= d; k++; i++)
v[i] = aux[k];
} // Complexidade: O(d - e + 1)
5. MergeSort
void mergesort(int *v, int e, int d){
if(e<d){
int m = (e + d) / 2;
mergesort(v, e, m);
mergesort(v, m+1, d);
intercala(v, e, m, d);
}
} // Complexidade O(n Lg n)
6. QuickSort
Baseia-se no problema da sepração. Dado um vetor v[e ... d], queremos um j tal que: $$ v[e .. j-1] <= v[j] < v[j+1..d] $$
Onde \(v[e .. j-1]\) e \(v[j+1..d]\), podem não estar ordenados.
Ex.: Estapas do quicksort
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
v = | 2 | -1 | 0 | 3 | 4 | 1 |
Onde, 1 é o pivô
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
v = | 0 | -1 | 1 | 3 | 4 | 2 |
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
v = | 0 | -1 | 1 | 2 | 4 | 3 |
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
v = | -1 | 0 | 1 | 2 | 3 | 4 |
Pior caso
O pior caso sera um vetor ordenado, pois ele não vai conseguir dividir o vetor, pois o pivô sempre vai estar no lugar certo.
Complexidade: \(O(n^2)\)
O algoritmo da separação
e | j | k | d | |||||
---|---|---|---|---|---|---|---|---|
v= | <=c | <=c | >e | ? | ? | ? | ? | ? |
Se \(v[k]<= c\), troca v[k] com v[j] e incrementa j.
int separa(int *v, int e, int d){
int c = v[d];
int j = e, k = e;
while(k < d){
if(v[k] <= c){
troca(&v[k], &v[j]);
j++;
}
}
k++;
troca(&v[j], &v[d]);
return j;
}
Algoritmo QuickSort
void quicksort(int *v, int e, int d){
if(e < d){
int p = separa(v, e, d);
quicksort(v, e, p-1);
quicksort(v,p+1, d);
}
}
Complexidade: \(O(n^2)\)
Observáveis
- O pior caso do QuickSort é quando separa sempre retorna d. Isso pode acontece quando o vetor já esteja ordenado.
- Há uma implementação do QuickSort em C, na stdlib.h.
void qsort(void *v, int n, int size_memb, int(compara)(void *a, void *b))
Temos um jeito de melhorar o quicksort, que é mudando o pivô, trocando com a mediana do vetor. Podemos usar uma função pra fazer isso:
int mediana3(int e, int m, int d){
int a = v[e], b = v[m], c = v[d];
}
void quicksort(int *v, int e, int d){
if(e<d){
int m = mediana3(e, (e+d)/2, d);
troca(&v[m], &v[d]);
int p = separa(v, e, d);
quicksort(v , e , p-1);
quicksort(v, p+1, d);
}
}
7. QuickSelect
Problema: encontrar o k-ésimo menor elemento de um vetor v[0 ... n-1], para \(0 <= k < m\).
void quickselect(int *v, int e, int d, int k){
if(e < d){
int m = mediana3(e, (e+d)/2, d);
troca(&v[m], &v[d]);
int p = separa(v, e, d);
if(k < p) quickselect(v, e , p-1, k);
if(k > p) quickselect(v, p+1 , d, k);
}
}
Observações
- O pior caso do QuickSelect é o mesmo do QuickSort em termos de instância e complexidade.
- Além de encontrar o k-ésimo menor elemento, o QuickSelect reordena os elementos de v tal que:
Isso pode ser muito eficiente para ordenar apenas uma parte do vetor.
Algoritmo de ordenações Lineares
1. Contagem
Premissa: O conjunto a ser ordenado possui apenas números inteiros no intervalo [a,b], com \(a,b \in \mathbb{Z}\).
Lógica: Usando um vetor auxiliar de tamanho \(|b - a| + 1\), conto a ocorrência de cada elemento no vetor e, ao final, exibo os elementos em ordem.
Ex.:
0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
-3 | 0 | 4 | -1 | -5 | 5 | 3 |
Nesse caso:
a = -5, b = 5, Logo |b-a| + 1 = 11
O vetor auxiliar:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
Na hora de printar:
0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
-5 | -3 | -1 | 0 | 3 | 4 | 5 |
Algoritmo
void contagem(int *v, int n, int a, int b){
int tam = b - a;
if(tam < 0) tam -= tam;
int *aux = calloc(tam + 1, sizeof(int));
for(int i = 0; i < n; i++) aux[v[i] - a];
for(int i=0, j=0; i<=tam; i++){ // *
while(aux[i] > 0){
v[j] = i + a; j++; aux--; //**
}
}
free(aux);
} //COMPLEXIDADE: O(|b-a| + 1)
Esse código compensa quando |b-a| + 1 for \(O(n)\).
Todavia o laço() é muito rápido, pois (*) só é feito n vezes. Logo, se há possibilidade de arcar com o custo de mamória o algoritmo é interessante.