Algoritmo De Ordenação

Há mais ou menos vinte anos atrás, em um processo seletivo, fui surpreendido por um teste que pedia para ordenar um vetor de "n" elementos. Eu conhecia pelo menos três algoritmos que faziam isso, e eram o QuickSort, o Bubblesort e o ShellSort. Na hora da prova, no entanto, não conseguia lembrar de nenhum deles.
Para resolver a questão, portanto, tive de criar, naquele momento, um algoritmo de ordenação próprio.  Fiz o teste e fui aprovado no processo seletivo.

Mais tarde verifiquei, para a minha surpresa, que criara algo inédito nessa área. Todos os algoritmos de ordenação conhecidos utilizam pelo menos dois laços (loop). O meu algoritmo utiliza somente um laço. É verdade que ele não é lá muito rápido, mas resolve o problema.

O melhor caso dele acontece quando o vetor já está ordenado. O pior caso acontece quando o vetor está ordenado em ordem decrescente.

Posteriormente irei complementar esse artigo com a análise da complexidade do pior caso, o melhor caso e o caso médio.

Segue o algoritmo "GideonSort":

1) Em pseudo código:

Início do algoritmo

     " i" é o contador da posiçao do vetor
     i = 0

     Enquanto houver elementos, percorra o vetor
          Se o conteúdo do elemento seguinte for maior que o atual
              Troque as suas posiçoes
               Reinicie o contador de posicao do vetor (i=0);
          Senão
              Aumente "i" de uma posiçao (i=i+1)
          fim-se
     Fim Equanto;
Fim do algoriimo

2) Em linguagem de programaçao java:


/**
* Um novo algoritmo de ordenação
* A new Sort Algorithm
* @author Gideon M. Gonçalves - Brazil, Rio de Janeiro - 2008
* e-mail: gideonmarinho@gmail.com
*/

public class GideonSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
       
            int[] vetor={4,3,5,7,2,1,6,8,9};
            Ordena(vetor);
            Imprime(vetor);

    }

    public static void Ordena(int[] vet)
    {
        int aux;  // retém o valor de vetor[i] para substituicao
        int i=0;
       
        while (i < vet.length-1)
        {
            if (vet[i+1] < vet[i]) {
                aux = vet[i];
                vet[i] = vet[i+1];
                vet[i+1] = aux;
                i=0;
            } else
                i++;
        }
    }
   
    public static void Imprime(int[] vet)
    {
        for (int i=0; i< vet.length; i++)
        {
            System.out.println(vet[i]);
        }
        
      }
}       

* * *