Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados I

Ordenação

Um dos problemas básicos em Computação é, considerando uma certa relação de ordem, ordenar um conjunto de valores. Aqui são mostrados dois métodos de ordenação: inserção e seleção.

De forma mais específica, dado o arranjo:
int a[]={50,20,30,10,40};
deseja-se organizar o arranjo de forma a obter: 10, 20, 30, 40, 50 (ou a ordem inversa). Uma das formas de se obter isso é mudar o contéudo do arranjo: nos elementos de menor índice ficam os menores valores e nos elementos de maior índice ficam os maiores valores. Isto significa que o arranjo fica ordenado em ordem crescente segundo a ordem dos índices.

Um dos métodos mais simples de ordenação é a seleção: encontre o menor valor em um arranjo e troque a posição dele com o valor que está na primeira posição, depois encontre o segundo menor valor e troque a posição dele com o valor na segunda posição. No caso do exemplo acima teriamos os seguintes passos:
arranjo dado: {50,20, 30, 10, 40}
1o. passo {10, 20, 30, 50, 40}
2o. passo {10, 20, 30, 50, 40}
3o. passo {10, 20, 30, 50, 40}
4o. passo {10, 20, 30, 40, 50}

A função abaixo mostra uma sugestão de implementação da ordenação por seleção:
void ordenaPorSelecao(int a[], int N){
  int i,j,aux,indMenor;
  for(i=0; i<N-1; i++){ //iteracao de cada posicao
    indMenor=i;
    for(j=i+1; j<N; j++)  //iteracao para selecionar [indice do] menor
      if(a[j]<a[indMenor]) indMenor=j;
    aux=a[i];
    a[i]=a[indMenor];
    a[indMenor]=aux;
    }
}

A função ordenaPorSelecao() recebe um ponteiro para um arranjo de inteiros (lembre-se que int a[] equivale a int *a) e utiliza a idéia descrita acima para a ordenação. A execução fica estruturada sob dois comandos for. O for mais externo marca  qual parte do arranjo já foi ordenada, o for mais interno varre a parte restante do arranjo para determinar o índice do menor elemento. Num dado momento da execução, o arranjo já se encontra ordenado da posição de índice 0 até a posição de índice i-1.

Outra idéia de ordenação dá origem ao algoritmo de ordenação por inserção. Considere somente um primeiro valor: ele já está ordenado. Considere dois valores: (i)eles já estão ordenados ou (ii)devemos deslocar um valor para dar lugar para o outro. A cada novo passo consideramos um novo elemento e achamos no arranjo, já parcialmente ordenado, onde ele deve ficar (em função de termos “arredado” os elementos que ainda não estão em lugar adequado. No caso do exemplo acima teriamos os seguintes passos:
arranjo dado: {50,20, 30, 10, 40}
1o. passo: {20,50,30,10,40}
2o. passo: {20,30,50,10,40}
3o. passo: {10,20,30,50,40}
4o. passo: {10,20,30,40,50}

A função abaixo mostra uma sugestão de implementação da ordenação por inserção:

void ordenaPorInsercao(int a[], int N){
    int i,j, aux;
    for(i=1; i<N; i++){ //iteracao de cada posição
      aux=a[i];
      j=i;
      while(j>0&&a[j-1]>aux) a[j]=a[--j];  //iteracao de “arredar”
      a[j]=aux;
    }
  }

No caso da função acima, temos dois comandos iterativos aninhados: um while dentro de um for. A cada iteração do for é considerado um novo elemento do arranjo. O while envolve duas condições (j>0) e (a[j-1]>aux): a primeira condição relaciona-se com o elemento considerado ser o menor de todos que já estão ordenados (j já atingiu 0 e o “arredamento” deve terminar), a segunda condição relaciona-se com o elemento considerado ser colocado em algum local do arranjo com índice j>0. A sugestão de implementação acima utiliza o seguinte comando de atribuição ) a[j]=a[--j];. O uso da atribuição ) a[j]=a[--j]; não é recomendado em função de depender da ordem de avaliação das expressões correspondentes às indexações do arranjo. Nos exercícios abaixo é pedida uma implementação menos arriscada

Exercícios:

1. Implemente a função OrdenaPorInsercao de forma menos arriscada com relação a atribuição que faz o ”arredamento” dos valores no arranjo a ser ordenado.
2. Implemente ambos os métodos para ordenar arranjos de Strings. Uma das formas de fazer isso é utilizar a função strcmp().
3. A implementação de um algoritmo de ordenação pode ordenar em ordem crescente ou decrescente. Implemente ambos os métodos para ordenação em ordem decrescente.
4. Implemente ambos os métodos para imprimir cada passo da ordenação. Veja se você consegue antecipar o que  acontece com diferentes entradas.
5. Implemente os dois métodos para ordenar um arranjo a partir de dois índices que são fornecidos como parâmetros:
   ordena(int a[], int indInf, int indSup)
   o arranjo a é ordenado somente no trecho a[indInf], a[indInf+1], ...a[indSup-2], a[indSup-1], ou seja, o trecho inclui a[indInf] mas não inclui a[indSup].
6. O método de ordenação por inserção pode ordenar utilizando a seguinte forma do while:
         while(a[j-1]>aux) a[j]=a[--j];
   Neste caso a implementação ordena apenas da posição de índice 1 até o final do arranjo deixando “livre” a posição de índice 0! Implemente esta variante da “inserção”. (deve ser usada a “sentinela”!)
7. Implemente ambos os métodos para ordenar de forma indireta. Na forma indireta o método recebe a referência para o arranjo mas não altera nenhum dos valores do arranjo. O método retorna uma permutação dos índices que ordena o arranjo recebido como argumento. Veja abaixo:

    int[] a={50,20,30,10,40};

    int[] ind=permutacaoDeOrdenacaoPorSelecao(a,5);
    for(i=0; i<5; i++)
      printf(“%d\n”,a[ind[i]]);

  int *permutacaoDeOrdenacaoPorSelecao(int[] a, int T){
    int *ai=(int*)malloc(sizeof(int)*T);
    int i;
    for(i=0; i<T; i++) ai[i]=i;
    ...
return ai;
No caso do arranjo acima a permutação que o ordena é {3,1,2,4,0}.