Odd-even sort

Da Wikipedia, l'enciclopedia libera.
Odd-even sort
Esempio di ordinamento di una lista di numeri casuali dell'algoritmo di ordinamento odd-even sort (pari-e-dispari)
Esempio di ordinamento di una lista di numeri casuali dell'algoritmo di ordinamento odd-even sort (pari-e-dispari)
Classe Algoritmo di ordinamento
Struttura dati Array
Caso peggiore temporalmente O(n^2)
Ottimale No

In informatica l'Odd-even sort (ordinamento pari-e-dispari) è un semplice algoritmo di ordinamento basato sul bubble sort, con cui condivide alcune caratteristiche. Esso opera comparando tutte le coppie dispari e pari degli elementi presenti in una lista e, se una coppia è nell'ordine sbagliato (il primo elemento è maggiore del secondo), scambia di posto i suoi elementi. Il controllo prosegue poi con le coppie di elementi adiacenti con posizione pari/dispari. L'algoritmo continua l'ordinamento alternando tra le comparazioni dispari/pari e pari/dispari finché tutta la lista non risulta ordinata.

L'Odd-even sort può essere considerato come una sorta di elaborazione in processi paralleli in cui ognuno dei processi utilizza il bubble sort ma iniziando l'ordinamento da punti diversi della list (gli indici dispari per il primo passaggio).

Pseudocodice[modifica | modifica sorgente]

L'algoritmo risulta solo leggermente più difficile da implementare rispetto al bubble sort. Quella che segue è una implementazione in pseudocodice (si assume l'uso di array con indice di partenza 0):

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