Sortiranje "par-nepar"

U informatici, odd–even sortiranje predstavlja relativno jednostavan algoritam za sortiranje i razvijen je pre svega za korišćenje na paralelnim procesorima sa lokalnom povezanošću. Spada u grupu algoritama koji sortiraju poredjenjem i sličan je Bubble sort-u, sa kojim deli mnoge karakteristike. Ideja je da se porede svi parovi indeksa (nepar,par) susednih elemenata niza i, ako je taj par u pogrešnom poretku (prvi veći od drugog) elementi menjaju mesta. U sledećem koraku se postupak ponavlja za parove indeksa (par, nepar). Koraci se smenjuju izmedju te dve vrste parova dok se niz ne sortira.

Sortiranje "par-nepar"

Namena sortiranje Struktura podataka Niz Vremenska kompl. O(n²)

Sortiranje na paralelnim procesorima

Kod paralelnih procesora, koji imaju jednu vrednost po procesoru i lokalnu povezanost s leva u desno, procesori istovremeno izvršavaju upoređivanje i razmenu sa svojim susedima, naizmenično sa parovima nepar-par i par-nepar. Ovaj algoritam je predstavio N. Haberman 1972. godine. i pokazalo se da je efikasan na ovakvim procesorima.

Algoritam poboljšava efikasnost u slučaju rada na mašinama koje podržavaju vise vrednosti po procesoru. U tzv. Baudet–Stevenson odd–even merge-splitting algoritmu svaki procesor sortira svoj podniz, koristeći bilo koji efikasan algoritam za sortiranje, a zatim vrši spajanje sortiranog podniza sa svojim susedom, koji vrši uparivanje (naizmenično uzimajući jednu, pa drugu vrstu parova u svakom koraku).

Batcher- ov odd-even merge sort algoritam

Sličan, ali efikasniji algoritam za sortiranje je tzv. Batcher- ov odd-even merge sort, koji koristi operacije compare–exchange i perfect-shuffle. Ovaj metod pokazao se efikasnim na paralelnim procesorima dalekog dometa konekcije.

Algoritam

Ispod je predstavljen algoritam za jednoprocesorske mašine, nalik Bubble sort- u, jednostavan ali ne baš efikasan. Podrazumevamo da indeksiranje počinje od nule.

/* Assumes a is an array of values to be sorted. */
var sorted = false;
while(!sorted)
{
    sorted=true;
    for(var i = 1; i < list.length-1; i += 2)
    {
        if(a[i] > a[i+1])
        {
            swap(a, i, i+1);
            sorted = false;
        }
    }

    for(var i = 0; i < list.length-1; i += 2)
    {
        if(a[i] > a[i+1])
        {
            swap(a, i, i+1);
            sorted = false;
        }
    }
}