Material didático para princípios de desenvolvimento de Algoritmos

Dizemos que um algoritmo de ordenação é estável se, e somente se, para todo par de dados x e y, se antes da ordenação x aparece antes de y (índice menor) e a chave de x for igual à chave de y, então após a ordenação x continuará antes de y.

O conceito de algoritmo de ordenação estável é útil quando os dados forem compostos por mais de uma chave, havendo ordem de importância entre elas. Por exemplo, em um livro existem capítulos e dentro cada capítulo podem existir várias seções. Desse modo, ao manter uma lista com informações sobre um livro, cada dado pode ter duas chaves, a chave primária seria o número do capítulo e a secundária a seção.

Um outro exemplo prático do ponto de vista da computação é o registro de duplas (x,y) que representem os índices de uma matriz (de dimensão 2). Usualmente tais matrizes são representadas na memória agrupadas por linhas (como indicado na figura 1), assim o elemento de índice (0,2) vem "antes" do elemento (1,2). Ou seja, neste caso seria natural usar como chave primária o primeiro índice.

Exemplo: lista formada por duas chaves.
Considere uma lista formada por pares do tipo (p,q) (cada dado) e suponha que a chave primária seja o primeiro item p e o segundo q seja a chave secundária.
Considere o algoritmo de ordenação AO(L,i), sendo o primeiro parâmetro L a lista e o segundo a chave a ser usada (i=0 => primária, i=1 => secundária).
Considere a lista da dados L := { (4,1), (1,1), (1,2), (3,4) }.
Assim, se AO(.,.) é estável, então AO(L,0)) produz-se a lista ordenada L := { (1,1), (1,2), (3,4), (4,1) }.
Em uma implementação, considere cp[] e cs[] como sendo os vetores com as chaves primárias e secundária, respectivamente. Neste caso, podemos notar que inicialmente o dado (1,1) aparece na posição 1, antes do dado (1,2) que aparece na posição 2, ou seja, cp[1] = cp[2] e cs[1] < cs[2]. Após a ordenação, estes dados mantiveram a ordem relativa inicial, (1,1) antes de (1,2).

Um exemplo de algoritmo estável é Seleção Direta. Note na função ordenaViaSelecaoDireta que a linha do comando if (menor>dados[jj]) define o índice para o menor elemento. Nessa linha, havendo vários elementos que empatam como menores será selecionado o primeiro deles. Razão da estabilidade do método.

#include <stdio.h>
#define MAX 60
#define INTERVALO 10  // para gerar valores pseudo-aleatorios (modulo 100 => numeros entre 0 e 99)
#define troquePar(V, IA, IB) {Item t = V[IA]; V[IA] = V[IB]; V[IB] = t;} // {Item t = A; A = B; B = t;}
typedef int Item;

void imprimaDados (int vet1[], int vet2[], int n) {
  int ii;
  for (ii = 0; ii < n; ii++)
    printf(" (%3d,%d)", vet1[ii], vet2[ii]);
  printf("\n");
  }

int determineIndiceDoMenor (int vet[], int ini, int n) {
  int indice, menor, i;
  indice = ini;
  return indice; // indice do menor entre vet[ini .. n-1]
  }

// Ordena via Selecao Direta usando o primeiro vetor (dado[])
void ordenaViaSelecaoDireta (int dados[], int vaux[], int n) {
  int ii, jj, imin, menor, aux1, aux2;
  for (ii = 0; ii < n-1; ii++) { // invariante: dados[0]<=dados[1]<=...<=dados[ii-1] <= dados[j], j em { ii, ii+1, ..., n-1 }
    // imin = determineIndiceDoMenor(dados, ii, n);
    menor = dados[ii];
    for (jj=ii+1; jj<n; jj++) { // invariante: dados[imin] <= dados[j], j em { ii, ii+1, ii+2, ... jj-2, jj-1 }
      if (menor>dados[jj]) { // novo menor
        menor = dados[jj];
        imin = jj;
        }
      } // complexidade: O(n)
    troquePar(dados, ii, imin); // troque 'dados[ii]' com 'dados[imin]'
    troquePar(vaux,  ii, imin); // idem para 'vaux[.]'
    }
  } // complexidade: O(n^2)

int main (int argc, char *argv[])  {
  int cp[MAX], cs[MAX];
  int n, ii;

  if (argc < 2) {
    printf("Faltou o numero de elementos! Digite './ordena_dupla_selecao N'\n ");
    return 1; // erro
    }

  n = atoi(argv[1]); // converte primeiro parametro para inteiro
   
  printf("\n\nDados iniciais:\n");
  // scanf ("%d", &n); for (ii = 0; ii < n; ii++) scanf("%d", &dados[ii]);
  for (ii=0; ii<n; ii++) {
    cp[ii] = rand() % INTERVALO;
    cs[ii] = rand() % INTERVALO;
    printf(" (%3d,%d)", cp[ii], cs[ii]);
    }

  // Ordena pela chave secundaria (menos significativa)
  ordenaViaSelecaoDireta(cs, cp, n);
  printf("\n\nVetor ordenado por chave 1:\n");
  imprimaDados(cp, cs, n);

  // Ordena pela chave primaria (mais significativa)
  ordenaViaSelecaoDireta(cp, cs, n);
  printf("\n\nVetor ordenado por chave 0:\n");
  imprimaDados(cp, cs, n);

  printf("\n");
  return 0;
  }

No programa acima, o vetor vP[] contém as chaves primárias, enquanto o vS[] contém a chave secundária. Assim, o algoritmo ordena o par de vetores (vP[],vS[]), primeiro usando vS[] e depois ordena pelo vetor vP[] e respeita a propriedade de estabilidade:

se o dado x estiver na posição inicial i1 e       o dado y estiver na posição inicial j1, sendo que vP[i1]=vP[j1] e vS[i1]<vS[j1], então, ao final, o dado x terá índice i2 menor que o índice j2 do dado y, ou seja, i2 < j2 Portanto, x e y estarão relativamente ordenados: (vP[i2] , vS[i2]) antes de (vP[j2] , vS[j2]).

Assim, usando representação por coordenadas cartesianas e supondo que a chave primária seja a primeira componente e que os dados iniciais sejam

Note que o par (3,5) está na posição 2, antes do (3,6) na posição 4. Após a ordenação pela chave primária, o resultado é o vetor

Leônidas de Oliveira Brandão
http://line.ime.usp.br