9

Normalmente aprendemos na faculdade que, para ordenar vetores inteiros, usamos uma técnica chamada bubble sort:

int[] vetorOrdenado = new int[8];

    vetorOrdenado[0] = 2;
    vetorOrdenado[1] = 41;
    vetorOrdenado[2] = 12;
    vetorOrdenado[3] = 6;
    vetorOrdenado[4] = 5;
    vetorOrdenado[5] = 29;
    vetorOrdenado[6] = 17;
    vetorOrdenado[7] = 3;

    for(int i = 0; i < vetorOrdenado.length;i++){
        for(int j = 0; j < vetorOrdenado.length - 1; j++){
            if(vetorOrdenado[i] < vetorOrdenado[j]){
                int aux = vetorOrdenado[i];
                vetorOrdenado[i] = vetorOrdenado[j];
                vetorOrdenado[j] = aux; 
            }

        }
    }

Essa técnica ordena um vetor de inteiros, como pode ser visto no ideone.

Há outra maneira de se ordenar vetores numéricos sem utilizar laço dentro de laço, como no bubble sort? Collections não possui alguma forma de ordenar um vetor dessa forma?

4

1 Resposta 1

5

O algoritmo de ordenação mais usado é disparado o Quicksort. Ele não é bom para todos os casos, mas é bom em muitos e os mais comuns. A não ser que precise de performance extrema e sabe que o padrão típico dos dados se adéqua melhor para outros algoritmos é ele que deve ser escolhido.

O Java que não é bobo usa-o há muito tempo em uma otimização específica para aumentar o número de casos onde ele é adequado. Isto está disponível na própria API do array.

Para casos onde uma coleção precisa ser analisada contra ele mesma, tudo o que não se quer é uma complexidade O(N2), que é o comum neste caso. E o QS permite na maioria dos casos O(N logN), que é o melhor que se pode esperar no caso geral.

O Radix pode ser melhor ainda, mas é difícil implementá-lo.

Comparação dos algoritmos.

Coloquei no GitHub para referência futura.

Você deve fazer log-in para responder a esta pergunta.