Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м Bot: Pretvaranje običnih izvora koristeći ref imena da bi se izbjegli duplikati (pogledaj također FAQ)
м Робот: додато {{subst:User:Autobot/sandbox2}}
Ред 1:
{{loš seminarski}}
{{Infobox Algorithm
{{спајање|Непарно-парно сортирање}}
|class=[[Алгоритам сортирања]]
{{algoritam-lat
|image=[[Датотека:Odd even sort animation.gif|Пример парно непарно сортирања у низу са насумичним бројевима.|Пример парно непарно сортирања у низу са насумичним бројевима.]]
| slika=Odd even sort animation.gif
|caption=Пример парно непарно сортирања у низу са насумичним бројевима.
| širina slike=250
|data=[[Array data structure|Низ]]
| struktura=[[Niz]]
|time=<math>O(n^2)</math>
| namena=[[Алгоритми сортирања|sortiranje]]
|best-time=<math>O(n)</math>
| vkompleksnost= ''-{[[Велико O|O]](n²)}-''
|space= <math>O(1)</math>
|optimal=No
}}
У рачунарству непарно-парно сортирање или парно-непарно сортирање је релативно једноставан алгоритам, који је направљен за коришћење паралелних процесора са локалним међувезама. Ово је алгоритам који има велике сличности са [[Баблсорт|баблсорт алгоритмом]]<ref name="баблсорт алгоритам">{{cite book|quote=Врста алгоритма који се користи за сортирање}}</ref>, са којим има доста карактеристика. Функционише тако што упоређује парне/непарне индексиране парове суседних елемената у листи, и ако су елементи на погрешним позицијама (ако је други елемент већи од првог)алгоритам врши замену. У следећем кораку се ово исто извршава за све суседне парно/непарне индексиране парове. Онда алгоритам алтернира између непарних/парних и парно/непарних коракасве док листа није потпуно сортирана.
== Сортирање процесорских листа ==
[[Датотека:Oddeven.gif|оквир|Пример рада алгоритма непарно-парног сортирања]]
На паралелним процесорима, са једним елементом по процесору и само левом-десном локалном комшиском везом, процесори истовремено раде операције упоређивања и замене, алтернирајући између непарно/парне и парне/непарне парове. Овај алгоритам је оригинално представљен, и показано је да ефикасно ради на оваквим процесорима од старане Хабермана 1972. године.
 
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.
 
== 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>
function oddEvenSort(list) {
{{citation
| journal = Advances in computers
| editors = Franz L. Alt and Marshall C. Yovits
| title = Parallel Sorting Algorithms
| author = S. Lakshmivarahan, S. K. Dhall, and L. L. Miller
| 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 ==
function swap( list, i, j ){
 
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>
var temp = list[i];
{{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
| author = Allen Kent and James G. Williams
| 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>
 
== Algoritam ==
list[i] = list[j];
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.
 
list[j] = temp;
 
}
 
var sorted = false;
 
while(!sorted)
 
{
 
sorted = true;
 
<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])
 
if(list[i] > list[i+1]){
swap(a, i, i+1);
 
{ sorted = false;
}
 
swap(list, i, i+1);
 
sorted = false;
 
}
 
}
 
for(var i = 0; i < list.length-1; i += 2)
 
{
if(a[i] > a[i+1])
 
if(list[i] > list[i+1]){
swap(a, i, i+1);
 
{ sorted = false;
}
 
swap(list, i, i+1);
 
sorted = false;
 
}
 
}
 
}
 
}<br /><ref name="Сортирање">{{cite book|last=Шкарић|first=Милан|title=Увод у програмирање|publisher=Микро књига|location=Београд|quote=Имплементација Парног непарног сортирања у програмском језику ц}}</ref>
 
Имплементација у програмски језк 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>
 
== Reference ==
Иплементација у PHP:
{{reflist}}
 
== Literatura ==
<source lang="php">
* {{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}}
function oddEvenSorting(&$a) {
* {{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}}
$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>
 
Имплементација у Пајтону:
 
<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>
 
Пример имплементације у матлабу:
 
<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>
 
== Референце ==
 
{{reflist}}
# 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 овде]
# Алгоритми и структуре података - Мило Томашевић
# Увод у програмирање - Милан Шкарић
 
[[Категорија:АлгоритамАлгоритми сортирања]]
[[Категорија:АлгоритамСтабилно сортирањасортирање]]
[[Категорија:Низови]]
[[Категорија:Низови и редови]]
Преузето из „https://sr.wikipedia.org/wiki/Sortiranje_%22par-nepar%22”