Home RecentChanges

Lesson08

Problema da ordenação:

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:

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:

  1. procura o menor elemento entre i e r, e identifica a posição min desse elemento;
  2. se o menor valor — guardado na posição min — for menor que o valor guardado na posição i, troca o a[i] com o a[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:

  1. os elementos nas $i-1$ posições anteriores já estão ordenados;
  2. 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 primeiros i elementos 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).