Algoritmo De Ordenação

Há muito tempo 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 isto, 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 nesta área. Todos os algoritmos de ordenação conhecidos utilizam pelo menos dois laços (loop). Este novo algoritmo utiliza somente um laço. É verdade que ele não é lá muito rápido, mas resolve o problema.

O melhor caso deste novo algoritmo de ordenação acontece quando o vetor já está ordenado em ordem crescente. 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

    Posicione o vetor na primeira posição

     Enquanto houver elementos, percorra o vetor até a penúltima posição
          Se o conteúdo do elemento seguinte for maior que o conteúdo da posição atual do vetor
              Troque as suas posiçoes
              Volte para a primeira posição do vetor
          Senão
              Vá para a próxima posição do vetor 
          fim-se
     Fim Equanto;
Fim do algoritmo

2) Em linguagem de programaçao java:

/*
 * GideonSort.java
 *
*/

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

class GideonSort {
 void sort(int vetor[]) trows Exception {
 int i = 0; // Contador de elementos do vetor
 int temp; // recebe temporariamente um elemento para troca de posicao
 int tam = vetor.length; // Tamanho do vetor

 while(i < tam){ 
 if (vetor[i+1] < vetor[i]) {
 temp = vetor[i];
 vetor[i] = vetor[i+1];
 vetor[i+1] = temp;
 i=0;
 }
 else
 i++;
 }
 }
}