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 o primeiro valor, ele já está ordenado. Considere o primeiro e o segundo valores, se o segundo for maior então desloque o primeiro valor para onde estava o segundo e coloque o segundo onde estava o primeiro. A cada novo passo consideramos um novo elemento e achamos no arranjo, já parcialmente ordenado, onde ele deve ficar. 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}.