Odd-even sort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Odd-even sort

Captura de tela
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso O(n^2)
otimo não
Algoritmos

O Odd-even sort é um algoritmo de ordenação relativamente simples. É um algoritmo de ordenação por comparação baseado no bubble sort com o qual compartilha muitas características. Ele funciona através da comparação de todos os pares indexados (ímpar, par) de elementos adjacentes na lista e, se um par está na ordem errada (o primeiro é maior do que o segundo), os elementos são trocados. O próximo passo repete isso para os pares indexados (par, ímpar) (de elementos adjacentes). Em seguida, ele alterna entre etapas de (ímpar, par) e (par, ímpar) até que a lista é ordenada. Pode ser pensado como a utilização de processadores paralelos, cada qual usando um BubbleSort, mas a partir de diferentes pontos na lista (todos os índices ímpares para a primeira etapa). Este algoritmo de ordenação é apenas ligeiramente mais difícil do que o bubble sort para implementar.

Pseudocódigo[editar | editar código-fonte]

Um índice baseado-em-zero é assumido.

     sorted = false;
     while not sorted
       sorted = true;
           // odd-even
           for ( x = 1; x < list.length-1; x += 2)
              if list[x] > list[x+1]
                 swap list[x] and  list[x+1]
                 sorted = false;
           // even-odd
           for ( x = 0; x < list.length-1; x += 2)
              if list[x] > list[x+1]
                 swap list[x] and  list[x+1]
                 sorted = false;