Odd-even sort
Odd-even sort | |
---|---|
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 | |
Ottimale | No |
Manuale |
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 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
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;
V · D · M | ||
---|---|---|
Teoria | Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo | |
Algoritmi a scambio | Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort | |
Algoritmi di selezione | Selection sort · Heap sort · Smoothsort | |
Algoritmi ad inserimento | Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting | |
Algoritmi a fusione | Merge sort · Timsort | |
Algoritmi non comparativi | Radix sort · Bucket sort · Counting sort · Pigeonhole sort | |
Altri algoritmi | Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle | |
Algoritmi inefficienti | Stupid sort · Trippel sort |