Sortiranje "par-nepar"

Из Википедије, слободне енциклопедије
(преусмерено са Par-nepar sortiranje)
Sortiranje "par-nepar"
Odd even sort animation.gif
Namena sortiranje
Struktura podataka Niz
Vremenska kompl. O(n²)

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 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. Приступљено 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[уреди]