Изворни код странице Sortiranje "par-nepar"

{{algoritam-lat
| class= [[Algoritam sortiranja]]
| slika= Odd even sort animation.gif
| širina slike= 250
| struktura= [[Niz]]
| namena=[[Алгоритми сортирања|sortiranje]]
| vkompleksnost=  ''-{[[Велико O|O]](n²)}-''
| data=[[Array data structure|Низ]]
| time=<math>O(n^2)</math>
| best-time=<math>O(n)</math>
| space= <math>O(1)</math>
| optimal=No
}}

U [[informatika|informatici]], '''par-nepar sortiranje''' ({{jez-eng-lat|Odd–even sort}})<ref>{{cite web|last=Phillips|first=Malcolm|title=Array Sorting|url=http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging_Sort_Techniques|website=Homepages.ihug.co.nz|accessdate=3. 8. 2011|archive-url=https://web.archive.org/web/20111028201105/http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging_Sort_Techniques|archive-date=28. 10. 2011|url-status=dead|df=}}</ref> predstavlja relativno jednostavan [[Алгоритми сортирања|algoritam za sortiranje]], koji je prvenstveno razvijen za upotrebu na paralelnim procesorima sa lokalnom povezanošću. On spada u grupu [[algoritam]]a koji [[Алгоритми сортирања#Алгоритми сортирања поређењем|sortiraju poređenjem]] i sličan je [[Sortiranje mehurom|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.<ref>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).</ref> 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'' ({{jez-eng-lat|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).<ref>{{citation
 | journal = Advances in computers
 | editor = Franz L. Alt | editor2 = Marshall C. Yovits
 | title = Parallel Sorting Algorithms
 |author1=S. Lakshmivarahan |author2=S. K. Dhall |author3=L. L. Miller  |last-author-amp=yes | volume = 23
 | publisher = Academic Press|pages=295-351|isbn=978-0-12-012123-6
 |year=1984|url= http://books.google.com/books?id=Mo2Q-TEwKGUC&pg=PA322
 }}</ref>

== 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''.<ref>{{Cite book
 | title = Algorithms in Java, Parts 1-4
 | edition = 3rd
 | author = Robert Sedgewick
 | publisher = Addison-Wesley Professional
 |year=2003|isbn=978-0-201-36120-9|pages=454-464|url= http://books.google.com/books?id=hyvdUQUmf2UC&pg=PA455
 }}</ref>
Ovaj metod pokazao se efikasnim na paralelnim procesorima dalekog dometa konekcije.<ref>{{Cite book
 | title = Encyclopedia of Computer Science and Technology: Supplement 14
 |author1=Allen Kent  |last2=Williams|first2=James G.
  |lastauthoramp=yes | publisher = CRC Press
 |year=1993|isbn=978-0-8247-2282-1|pages=33-38|url= http://books.google.com/books?id=F9Y4oZ9qZnYC&pg=PA33
 }}</ref>

== Sortiranje procesorskih lista ==
[[Датотека:Oddeven.gif|мини|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 [[Sortiranje mehurom|sortiranja mehurom]] on je jednostavan ali nedovoljno efikasan. Podrazumevamo da indeksiranje počinje od nule.

<source lang="javascript">
/* 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;
        }
    }
}
</source>

== Implementacija ==
'''Pseudo kod'''<ref name="Сортирање">{{cite book|last=Škarić|first=Milan|title=Uvod u programiranje|publisher=Mikro knjiga|location=Beograd|quote=Implementacija Parnog neparnog sortiranja u programskom jeziku c}}</ref>

<source lang="javascript">
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;
      }
    }
  }
}
</source>

Implementacija u programskom jezk C++:

<source lang="cpp">
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]) ;
              } 
          }
    }
}
</source>

Iplementacija u PHP:

<source lang="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;
			}
		}
	}
}
</source>

Implementacija u [[Pajton]]u:

<source lang="python">
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
</source>

Primer implementacije u [[Matlab]]u:

<source lang="matlab">
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
</source>

== Reference ==
{{reflist}}

== Literatura ==
{{Литература}}
* {{Cite book |ref= harv|title = Encyclopedia of Computer Science and Technology: Supplement 14|author1=Allen Kent  |last2=Williams|first2=James G.  |lastauthoramp=yes | publisher = CRC Press|year=1993|isbn=978-0-8247-2282-1|url=http://books.google.com/books?id=F9Y4oZ9qZnYC&pg=PA33 |pages=33-38}}
* {{Cite book |ref= harv|title = Algorithms in Java, Parts 1-4| edition = 3rd |last=Sedgewick|first=Robert| publisher = Addison-Wesley Professional |year=2003|isbn=978-0-201-36120-9 |url=http://books.google.com/books?id=hyvdUQUmf2UC&pg=PA455|pages=454-464}}
* Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати [http://bayanbox.ir/view/4177858657730907268/introduction-to-algorithms-3rd-edition.pdf овде] {{Wayback|url=http://bayanbox.ir/view/4177858657730907268/introduction-to-algorithms-3rd-edition.pdf |date=20161018163830 }}
* Algoritmi i strukture podataka - Milo Tomašević
* Uvod u programiranje - Milan Škarić
{{Литература крај}}

{{normativna kontrola}}

[[Категорија:Алгоритми сортирања]]
[[Категорија:Стабилно сортирање]]
[[Категорија:Низови]]
[[Категорија:Низови и редови]]