Odd-even sort

Odd-even sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	${\displaystyle O(n^{2})}$
otimo	não
Algoritmos
Esta caixa: ver discutir

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

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;