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}

O programa abaixo mostra uma sugestão de implementação do método de ordenação por seleção:
class selecao{
  public static void main(String[] args){
    /* declara e inicializa um arranjo */
    int[] ai={0, 50,20,30,10,40};
    /* ordena o arranjo */
    ordenaPorSelecao(ai);
    for(int i=1; i<ai.length; i++)
      System.out.print(ai[i]+" ");
    System.out.println();
  }

static void ordenaPorSelecao(int[] a){
int aux,indMenor;
    for(int i=1; i<a.length-1; i++){
indMenor=i;
      for(int j=i+1; j<a.length; j++)
        if(a[j]<a[indMenor]) indMenor=j;
      aux=a[i]; a[i]=a[indMenor];
      a[indMenor]=aux;
    }
  }
}

O método estático ordenaPorSelecao() recebe uma referência para um arranjo de inteiros e utiliza a idéia descrita acima para a ordenação. Neste programa a posição de índice 0 do arranjo não é incluída na 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 1 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}

O programa abaixo mostra uma sugestão de implementação do método de ordenação por inserção:

class insercao{
  public static void main(String[] args){
    /* declara e inicializa um arranjo */
    int[] ai={0, 50,20,30,10,40};
    /* ordena o arranjo */
    ordenaPorInsercao(ai);
    for(int i=1; i<ai.length; i++)
      System.out.print(ai[i]+" ");
    System.out.println();
  }

  static void ordenaPorInsercao(int[] a){
    int j;
    final int indSentinela=0;
    for(int i=2; i<a.length; i++){
      a[indSentinela]=a[i];
      j=i;
      while(a[j-1]>a[indSentinela]) a[j]=a[--j];
      a[j]=a[indSentinela];
    }
  }
}

Ambos os métodos apresentados ordenam arranjos de inteiros e não envolvem na ordenação o elemento de índice 0. No caso do método acima, temos dois comandos iterativos aninhados: um while dentro de um for. A cada iteração do for é considerado um novo elemento do arranjo. A condição do comando while não precisa testar se foi atingida a extremidade do arranjo: a posição de índice 0 do arranjo contém um valor que garante a quebra da iteração do while.

Exercícios:

1. Implemente ambos os métodos para ordenar arranjos de Strings.
2. A implementação de um algoritmo de ordenação pode ordenar em ordem crescente ou decrescente e pode ainda ordenar do início do arranjo para o final ou ainda do final para o início. Implemente ambos os métodos segundo a tabela abaixo:

	ordem crescente	ordem decrescente
ordenação a partir do início	Dado	Exercício (a)
ordenação a partir do final	Exercício (b)	Exercício (c)

3. Implemente ambos os métodos para incluir na ordenação o elemento de índice 0.
4. 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:

class ordenaindselecao{
  public static void main(String[] args){
int[] a={50,20,30,10,40};

int[] ind=permutacaoDeOrdenacaoPorSelecao(a);
    for(int i=0; i<a.length; i++)
System.out.println(a[ind[i]]);
  }

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