Sortiranje "par-nepar"

U informatici, par-nepar sortiranje (engl. Odd–even sort)[1] 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 "par-nepar"
Odd even sort animation.gif
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.[2] 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 (engl. Baudet–Stevenson odd–even merge-splitting) 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).[3]

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.[4] Ovaj metod pokazao se efikasnim na paralelnim procesorima dalekog dometa konekcije.[5]

Sortiranje procesorskih listaУреди

 
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[6]

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Уреди

  1. ^ Phillips, Malcolm. „Array Sorting”. Homepages.ihug.co.nz. Архивирано из оригинала на датум 28. 10. 2011. Приступљено 3. 8. 2011. 
  2. ^ 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).
  3. ^ S. Lakshmivarahan; S. K. Dhall & L. L. Miller (1984), Franz L. Alt & Marshall C. Yovits, ур., „Parallel Sorting Algorithms”, Advances in computers, Academic Press, 23: 295—351, ISBN 978-0-12-012123-6 
  4. ^ Robert Sedgewick (2003). Algorithms in Java, Parts 1-4 (3rd изд.). Addison-Wesley Professional. стр. 454—464. ISBN 978-0-201-36120-9. 
  5. ^ Allen Kent & Williams, James G. (1993). Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. стр. 33—38. ISBN 978-0-8247-2282-1. 
  6. ^ Škarić, Milan. Uvod u programiranje. Beograd: Mikro knjiga. »Implementacija Parnog neparnog sortiranja u programskom jeziku c« 

LiteraturaУреди