Википедија

Sortiranje "par-nepar" — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
м Разне исправке
Нова страница: {{Infobox Algorithm |class=Алгоритам сортирања |image=File:Odd even sort animation.gif|Пример парно непарно сортирања…
Ред 1:
{{Infobox Algorithm
{{algoritam-lat
|class=[[Алгоритам сортирања]]
| slika=Odd even sort animation.gif
|image=[[File:Odd even sort animation.gif|Пример парно непарно сортирања у низу са насумичним бројевима.|Пример парно непарно сортирања у низу са насумичним бројевима.]]
| širina slike=250
|caption=Пример парно непарно сортирања у низу са насумичним бројевима.
| struktura=[[Niz]]
|data=[[Array data structure|Низ]]
| namena=[[Алгоритми сортирања|sortiranje]]
|time=<math>O(n^2)</math>
| vkompleksnost= ''-{[[Велико O|O]](n²)}-''
|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|accessdate = 3. 8. 2011.}}</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.
На паралелним процесорима,са једним елементом по процесору и само левом-десном локалном комшиском везом,процесори истовремено раде операције упоређивања и замене,алтернирајући између непарно/парне и парне/непарне парове.Овај алгоритам је оригинално представљен,и показано је да ефикасно ради на оваквим процесорима од старане Хабермана 1972. године.<br />
 
== Имплементација ==
== Sortiranje na paralelnim procesorima ==
'''Псеудо код'''<br />
 
function oddEvenSort(list) {<br />
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.
function swap( list, i, j ){<br />
 
var temp = list[i];<br />
[[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>
list[i] = list[j];<br />
{{citation
list[j] = temp;<br />
| journal = Advances in computers
}<br />
| editors = Franz L. Alt and Marshall C. Yovits
var sorted = false;<br />
| title = Parallel Sorting Algorithms
while(!sorted)<br />
| author = S. Lakshmivarahan, S. K. Dhall, and L. L. Miller
{<br />
| volume = 23
sorted = true;<br />
| publisher = Academic Press|pages=295-351|isbn=978-0-12-012123-6
for(var i = 1; i < list.length-1; i += 2)<br />
|year=1984|url= http://books.google.com/books?id=Mo2Q-TEwKGUC&pg=PA322
}} {<br /ref>
if(list[i] > list[i+1])<br />
 
{<br />
== Bačerovo par-nepar sortiranje spajanjem ==
swap(list, i, i+1);<br />
 
sorted = false;<br />
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>
}<br />
{{Cite book
}<br />
| title = Algorithms in Java, Parts 1-4
for(var i = 0; i < list.length-1; i += 2)<br />
| edition = 3rd
{<br />
| author = Robert Sedgewick
if(list[i] > list[i+1])<br />
| publisher = Addison-Wesley Professional
{<br />
|year=2003|isbn=978-0-201-36120-9|pages=454-464|url= http://books.google.com/books?id=hyvdUQUmf2UC&pg=PA455
swap(list, i, i+1);<br />
}}</ref>
sorted = false;<br />
Ovaj metod pokazao se efikasnim na paralelnim procesorima dalekog dometa konekcije.<ref>
}<br />
{{Cite book
}<br />
| title = Encyclopedia of Computer Science and Technology: Supplement 14
}<br />
| author = Allen Kent and James G. Williams
}<br />
| publisher = CRC Press
== Референце ==
|year=1993|isbn=978-0-8247-2282-1|pages=33-38|url= http://books.google.com/books?id=F9Y4oZ9qZnYC&pg=PA33
# 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 овде]
}}</ref>
# Алгоритми и структуре података - Мило Томашевић
 
# Увод у програмирање - Милан Шкарић
== 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>
 
== Reference ==
{{reflist}}
 
== Literatura ==
* {{Cite book |ref= harv|title = Encyclopedia of Computer Science and Technology: Supplement 14|author=Allen Kent and James G. Williams | publisher = CRC Press|year=1993 |isbn=978-0-8247-2282-1|url=http://books.google.com/books?id=F9Y4oZ9qZnYC&pg=PA33|ref=harv|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}}
 
[[Категорија:Алгоритми сортирања]]
[[Категорија:Стабилно сортирање]]
Преузето из „https://sr.wikipedia.org/wiki/Sortiranje_%22par-nepar%22”