Odd-Even Sort

Odd-Even Sort

Maurício Barbosa, Marciano Junior, Cristiano Castro, Leonardo Trevisan

O método de ordenação Odd-Even Sort é relativamente simples, sendo uma derivação do método de ordenação Bubble Sort. Este último percorre os elementos comparando todas as duplas (elementos que estão lado a lado), trocando ele quando estão em desordem (primeiro elemento da dupla maior que o segundo). O diferencial do Odd-Even Sort, é que ele não compara todas as duplas.
Primeiramente ele percorre os elementos comparando somente as duplas de elementos ímpar-par, ou seja, compara o elemento da posição 1 com o elemento da posição 2, depois o elemento da posição 3 com o elemento da posição 4 e assim por diante, até que tenha percorrido todos elementos. Então ele faz um processo semelhante, mas iniciando pelo elemento 0, dessa forma comparando os elementos de posição par com elementos de posição ímpar (compara 0 com 1, então 2 com 3, etc.) até chegar ao fim dos elementos. Nas comparações, sempre que o primeiro elemento da dupla comparada for maior que o segundo, eles são trocados. Este algoritmo não é inteligente, caso somente a última dupla de elementos esteja fora de ordem, ainda assim serão realizados mais dois laços de ordenação (odd-even e even-odd), sem alterar qualquer elemento. Ele percorre os elementos duas vezes (com exceção do primeiro e do último elementos que são percorridos somente uma vez) e, caso ao menos um elemento precise ser ordenada, os dois laços serão executados novamente, pois será realmente necessário em casos onde o elemento que está na primeira posição é o maior dentre todos os demais. A grande utilidade deste método de ordenação é a possibilidade de se usar múltiplos processadores para ordenar uma lista, pois nos laços cada dupla de elementos é ordenada de forma isolada. Tanto no odd-even quanto no even-odd a lista pode ser dividida em duas partes para que cada processador realize uma metade. A performance é terrível quando o número de