U informatici, par-nepar sortiranje () predstavlja relativno jednostavan algoritam za sortiranje, koji je prvenstveno razvijen za upotrebu na paralelnim procesorima sa lokalnom povezanošću. On spada u grupu algoritama koji sortiraju poređenjem i sličan je sortiranju mehurom, 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 između te dve vrste parova dok se niz ne sortira.
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.N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151). i pokazalo se da je efikasan na ovakvim procesorima.
Algoritam poboljšava efikasnost u slučaju rada na mašinama koje podržavaju više vrednosti po procesoru. U tzv. algoritmu Bodet-Stevensonovog par-nepar spajanja-razdvajanja () 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).
Bačerovo par-nepar sortiranje spajanjem
Sličan, ali efikasniji algoritam za sortiranje je tzv. Bačerovo par-nepar sortiranje spajanjem, koji koristi operacije uporedi–razmeni i perfektno mešanje. Ovaj metod pokazao se efikasnim na paralelnim procesorima dalekog dometa konekcije.
Sortiranje procesorskih lista мини|250px|Primer rada algoritma neparno-parnog sortiranja Na paralelnim procesorima, sa jednim elementom po procesoru i samo levom-desnom lokalnom komšiskom vezom, procesori istovremeno rade operacije upoređivanja i zamene, alternirajući između neparno/parne i parne/neparne parove. Ovaj algoritam je originalno predstavljen, i pokazano je da efikasno radi na ovakvim procesorima od starane Habermana 1972. godine.
Algoritam Ispod je predstavljen algoritam za jednoprocesorske mašine. Poput sortiranja mehurom on je jednostavan ali nedovoljno 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;
Implementacija Pseudo kod
function oddEvenSort(list) { function swap( list, i, j ){ var temp = list[i]; list[i] = list[j]; list[j] = temp;
var sorted = false; while(!sorted)
sorted = true; for(var i = 1; i < list.length-1; i += 2)
if(list[i] > list[i+1])
swap(list, i, i+1); sorted = false;
for(var i = 0; i < list.length-1; i += 2)
if(list[i] > list[i+1])
swap(list, i, i+1); sorted = false;
Implementacija u programskom jezk C++:
template <class T> void OddEvenSort (T a[], int n) { for (int i = 0 ; i < n ; i++)
if (i & 1) // 'i' је непар
for (int j = 2 ; j < n ; j += 2)
if (a[j] < a[j-1]) swap (a[j-1], a[j]) ;
else
for (int j = 1 ; j < n ; j += 2)
if (a[j] < a[j-1]) swap (a[j-1], a[j]) ;
Iplementacija u PHP:
function oddEvenSorting(&$a) { $n = count($a); $sorted = false; while (!$sorted) { $sorted = true; for ($i = 1; $i < ($n - 1); $i += 2) { if ($a[$i] > $a[$i + 1]) { list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]); if ($sorted) $sorted = false;
for ($i = 0; $i < ($n - 1); $i += 2) { if ($a[$i] > $a[$i + 1]) { list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]); if ($sorted) $sorted = false;
Implementacija u Pajtonu:
def oddevenSort(x): sorted = False while not sorted: sorted = True
for i in range(0, len(x)-1, 2): if x[i] > x[i+1]: x[i], x[i+1] = x[i+1], x[i] sorted = False for i in range(1, len(x)-1, 2): if x[i] > x[i+1]: x[i], x[i+1] = x[i+1], x[i] sorted = False return x
Primer implementacije u Matlabu:
function x = oddevenSort(x) sorted = false; n = length(x); while ~sorted sorted = true; for ii=1:2:n-1 if x(ii) > x(ii+1)
[x(ii), x(ii+1)] = deal(x(ii+1), x(ii)); sorted = false; end end for ii=2:2:n-1 if x(ii) > x(ii+1) [x(ii), x(ii+1)] = deal(x(ii+1), x(ii)); sorted = false; end end end
Reference
Literatura
Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати овде Algoritmi i strukture podataka - Milo Tomašević Uvod u programiranje - Milan Škarić
Категорија:Алгоритми сортирања Категорија:Стабилно сортирање Категорија:Низови Категорија:Низови и редови