Problema da ordenação:
- Entrada: um vector de elementos comparáveis segundo uma relação de ordem total.
- Objectivo: ordenar os elementos no vector (de forma crescente) segundo a relação de ordem considerada.
- Saída: o vector ordenado.
Existem inúmeros algoritmos de ordenação. Nesta aula vamos estudar alguns dos algoritmos de ordenação elementares que, não sendo os mais eficientes, são na práctica fáceis de codificar e por vezes suficientes. Em particular os algoritmos elementares podem ser rápidos/eficientes e competitivos para problemas de pequena e média dimensão, podendo ser os melhores em certas situações. Do ponto de vista pedagógico, os algoritmos elementares constituem bons exemplos para aprender a terminologia e o contexto dos problemas, e alguns são fáceis de generalizar para algoritmos mais eficientes ou úteis para melhorar o desempenho de outros algoritmos.
Na análise de desempenho dos algoritmos de ordenação teremos de ter em conta o tempo de execução, no caso dos algoritmos elementares temo em geral $O(N^2)$ tempo para ordenar $N$ elementos, e teremos de ter também em conta o espaço necessário, e.g., a ordenação pode ocorrer in-place ou com recurso a memória auxiliar.
Algoritmos de ordenação estáveis
Um algoritmo de ordenação é dito estável se preserva a ordem relativa dos elementos com chaves repetidas. Por exemplo, no caso de estarmos a ordenar uma lista de alunos por ano de graduação, mas que já foi previamente ordenada por nome, podemos preferir utilizar um algoritmo estável para termos a garantia de que os alunos em cada ano de graduação fiquem também ordenados por nome.
Notar que os algoritmos elementares são em geral estáveis, mas poucos algoritmos avançados o são.
Algoritmos de ordenação internos e externos
Um algoritmo de ordenação é dito interno se o conjunto de todos os dados a ordenar couber em memória RAM. Caso contrário é dito externo.
Notar uma distinção muito importante:
- ordenação interna pode aceder a qualquer dado com um custo muito pequeno;
- ordenação externa tem de aceder aos dados de forma sequencial (ou em blocos).
Vamos estudar apenas algoritmos de ordenação interna, embora alguns posso ser implementados como algoritmos externos de forma eficiente.
Algoritmos de ordenação: Implementação
Função sort implementa o algoritmo de ordenação:
void sort(int a[], int l, int r);
Esta função devolve a tabela a ordenada, entre as posições l e r.
int a[] /* * ---+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+--- * ... | 9 | 16 | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 10 | 11 | 13 | 15 | 18 | 6 | ... * ---+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+--- * l r */
Exemplo de utilização:
int main() {
int i, a[]={10,9,8,7,6,5,4,3,2,1};
sort(a, 0, 9);
for (i = 0; i < 10; i++)
printf("%3d ", a[i]);
printf("\n");
return 0;
}Outro exemplo de utilização em que o vector a é inicializado de forma aleatória:
#define N 10000
int main() {
int i, a[N];
for (i = 0; i < N; i++)
a[i] = 1000*(1.0*rand()/RAND_MAX);
sort(a, 0, N-1);
for (i = 0; i < N; i++)
printf("%3d ", a[i]);
printf("\n");
return 0;
}Abstracções úteis
Os elementos são ordenados por chave tendo em conta características específicas de cada elemento ou chave. Através de utilização das abstracções abaixo, assumimos que todos os algoritmos têm o mesmo comportamento igual.
typedef int Item;
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; }
#define compexch(A, B) if (less(B, A)) exch(A, B)Selection sort
Para cada elemento i entre as posições l e r:
- procura o menor elemento entre
ier, e identifica a posiçãomindesse elemento; - se o menor valor — guardado na posição
min— for menor que o valor guardado na posiçãoi, troca oa[i]com oa[min].
Implementação:
void selectionSort(int a[], int l, int r)
{
int i, j;
for (i = l; i < r; i++)
{
int aux, min = i;
/* Procura minimo. */
for (j = i+1; j <= r; j++)
if (a[j] < a[min])
min = j;
/* Troca elementos. */
aux = a[i]; a[i] = a[min]; a[min] = aux;
}
}Implementação genérica com recurso às abstracções definidas acima:
void selection(Item a[], int l, int r)
{
int i, j;
for (i = l; i < r; i++) {
int min = i;
for (j = i+1; j <= r; j++)
if (less(a[j], a[min]))
min = j;
exch(a[i], a[min]);
}
}Análise: a cada passo, escolher o menor entre os r−l−i+1 maiores elementos; para cada i, os primeiros i elementos ficam já na sua posição final; para cada valor de i do primeiro ciclo, o segundo ciclo é executado r−i vezes. Deste modo temos $N^2/2$ comparações e $N$ trocas. Quer pior caso quer no melhor caso temos um tempo $O(N^2)$, em que $N=r-l$.
O algoritmo tal como implementado não é estável devido à forma como seleccionamos o menor valor em cada passo. No entanto podemos alterar o algoritmo para que o mesmo seja estável.
Exercício: Considere o seguinte vector:
int v[ ] = {72, 29, 38, 22, 60, 2};Indique o conteúdo de v no final de cada passo do algoritmo selection sort.
Insertion sort
Para cada elemento i entre as posições l e r:
- os elementos nas $i-1$ posições anteriores já estão ordenados;
- mover o elemento na posição $i$ para a posição correcta entre os primeiros $i-1$ elementos por forma a que os $i$ elementos fiquem ordeandos. Notar que para cada
i, os primeirosielementos ficam ordenados, embora possam ainda não ficar na sua posição final. Isto significa em particular que, se o vector já estiver ordenado, fazemos apenas $N-1$ comparações e nenhuma troca.
Implementação (sem ciclo inicial):
void insertion(Item a[], int l, int r)
{
int i,j;
for (i = l+1; i <= r; i++) {
/* Variavel auxiliar para guardar o valor a[i] */
Item v = a[i];
j = i-1;
/* Enquanto v < a[j] puxar os valores para a direita */
while ( j>=l && less(v, a[j])) {
a[j+1] = a[j];
j--;
}
/* Guardar o valor originalmente na posicao i na posicao libertada */
a[j+1] = v;
}
}Exercício: Considere o seguinte vector:
int v[ ] = {72, 29, 38, 22, 60, 2};Indique o conteúdo de v no final de cada passo do algoritmo insertion sort.
Seja $N = r-l$. O tempo de execução deste algoritmo é $O(N^2)$ no pior caso que ocorre quando o vector está ordenado por ordem inversa. No melhor caso temos $O(N)$ que ocorre quando o vector já está ordenado da forma correcta. O algoritmo tal como implementado é estável.
Podemos alterar a implementação de forma a incluir um primeiro ciclo que coloca o menor valor na posição l, o qual depois serve como sentinela reduz as constantes de complexidade do segundo ciclo. Para cada i, os primeiros i elementos ficam ordenados, embora possam continuar ainda a não ficar na sua posição final.
Implementação com ciclo inicial:
void insertion(Item a[], int l, int r)
{
int i;
/* Coloca menor elemento na primeira posicao */
for (i = l+1; i <= r; i++)
compexch(a[l], a[i]);
for (i = l+2; i <= r; i++) {
int j = i;
/* Variavel auxiliar para guardar o valor a[i] */
Item v = a[i];
/* Enquanto v < a[j] puxar os valores para a direita */
/* Como o primeiro elemento e' o menor podemos omitir a condicao j>=l */
while (less(v, a[j-1])) {
a[j] = a[j-1];
j--;
}
/* Guardar o valor originalmente na posicao i na posicao libertada */
a[j] = v;
}
}Bubble sort
Implementação:
void bubble(Item a[], int l, int r)
{
int i, j;
for (i = l; i < r; i++)
for (j = l; j < l + r-i; j++)
compexch(a[j], a[j+1]);
}Para cada valor de i no primeiro ciclo, o segundo ciclo é executado r−i vezes Em cada iteração i há sempre um elemento (o r-i) que fica na sua posição final e, em particular, para cada i, os últimos i elementos ficam já na sua posição final. Só são efectuadas trocas entre elementos adjacentes.
Podemos também implementar da direita para a esquerda, caso que para cada i, os primeiros i elementos ficam já na sua posição final:
void bubble(Item a[], int l, int r)
{
int i, j;
for (i = l; i < r; i++)
for (j = r; j > i; j--)
compexch(a[j-1], a[j]);
}Exercício: Será que não haverá maneira de reduzir o número de iterações, em particular quando o vector já está parcialmente ordenado? Sim, introduzindo uma condição de paragem:
void bubble(Item a[], int l, int r)
{
int i, j, done;
for (i = l; i < r; i++){
done=1;
for (j = r; j > i; j--)
if (less(a[j], a[j-1])){
exch(a[j-1], a[j]);
done=0;
}
if (done) break;
}
}Exercício: Considere o seguinte vector:
int v[ ] = {72, 29, 38, 22, 60, 2};Indique o conteúdo de v no final de cada passo do algoritmo bubble sort (implementação da esquerda para a direita).