Sortirajuća mreža
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e9/SimpleSortingNetwork2.svg/250px-SimpleSortingNetwork2.svg.png)
U računarskim naukama, komparativne mreže su abstraktni uredjaji sačinjeni od određenog broja „žica“, koje sadrže neke vrednosti, i komparativnih modula koji povezuju parove žica i menjaju vrednosti na njima ako se ne nalaze u željenom odnosu. Takve mreže se najčešće konstruišu da bi se izvelo sortiranje odredjenog broja vrednosti i tada se nazivaju sortirajuće mreže.
Sortirajuće mreže se razlikuju od sortiranja metodom poredjenja u tome što one nisu sposobne da rade sa proizvoljno velikim unosima i u tome što se njihova sekvenca poređenja određuje unapred, bez obzira na ishod prošlih poređenja. Ta nezavisnot od sekvence poređenja je korisna pri paralelnom izvršavanju i u hardverskoj implementaciji. Bez obzira na jednostavnost sortirajućih mreža, teorija iza njih je iznenađujuće kompleksna. Njih su prvi put proučavali Arsmstrong, Nelson i O'Konor oko 1954. godine, koji su tada i stavili patent na tu ideju.[1]
Sortirajuće mreže se mogu implementirati preko hardvera i softvera. Donald Knut je opisao kako se poredjenja binarnih celih brojeva mogu implementirati kao jednostavni uredjaji sa tri stanja. Bečer je 1968, predložio da se sortirajuće mreže koriste za izradu prekidačkih mreža za računarski hardver, i da time zamene sve elekronske komponente i skuplje crossbar prekidače. U poslednjih 15 godina sortirajuće mreže, a naročito bitonik sort se koriste od strane GPGPU udruženja za izradu sortirajućih algoritama koji bi radili na grafičkim procesorskim jedinicama.[2]
Uvod
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Sorting-network-comparator-demonstration.svg/150px-Sorting-network-comparator-demonstration.svg.png)
Sortirajuća mreža se sastoji od dva tipa elemenata: komparatori i žice. Žice su predstavljene da idu sa leva na desno, noseći vrednosti (jedna vrednost po žici) koje se kreću mrežom u svakom trenutku. Svaki komparator povezuje dve žice. Kada par vrednosti koji putuje kroz par žica naiđe na komparator, komparator menja mesta vrednostima ako i samo ako je vrednost gornje žice veća od vrednosti donje.
Po formuli, ako gornja žica prenosi x, a donja y, onda će pošto nalete na komparator žice nose x’ = min(x,y) i
Potpuna operacija jednostavne sortirajuće mreže je prikazana ispod. Jasno se vidi zašto će ova mreža ispravno sortirati ulaze.
Dubina i efikasnost
Efikasnost sortirajuće mreže se može proceniti na osnovu njene veličine. Ona predstavlja broj komparatora ili neformalno dubinu koja je određena kao najveći broj komparatora koje jedna ulazna vrednost može da susretne svojim putem kroz mrežu. Ako uzmemo u obzir da sortirajuće mreže mogu da rade određena poređenja paralelno i ako pretpostavimo da svim poređenjima treba određena jedinica vremena, možemo reći da je dubina mreže jednaka broju koraka koji su potrebni da se izvrši.
Ubacivanje u mrežu i selekcija
Svaku mrežu možemo konstruisati rekurzivno na osnovu principa ubacivanja i selekcije. Ako pretpostavimo da imamo sortirajuću mrežu veličine n, možemo napraviti mreću veličine n+1 ubacujući dodatni broj u već sortiranu podmrežu (koristeći medote sortiranja umetanjem). Isto to možemo postići i selekcijom najniže vrednosti od ulaza i onda sortirati ostataka vrednosti rekurzivno (koristeći metode sortiranja mehurom).
![]() | ![]() |
Struktura ove dve sortirajuće mreže je veoma slična. Ako spojimo ove dve metode, vidimo preko komparacija koje mogu da se izvrše istovremeno da su čak i identične.[3]
![]() | ![]() | ![]() |
Ovakve mreže imaju veliku dubinu od 2n -3, što je čini nepraktičnom.
Iako je lako dokazati ispravnost nekih mreža kao u gore navedenim primerima to nije uvek tako. Postoji n! Permutacija u mreži sa n žica, i testiranje svih njih traje vrlo dugo, naročito ako je n veliki broj. Taj broj može značajno da se smanji do 2n , koristeći metod koji se zove nula-jedan.
Ovaj princip kaže da ako sortirajuća mreža može da sortira 2n niza nula i jedinica, onda može da sortira i proizvoljne brojeve u istom vremenu. Ovo ne samo da smanjuje testiranje ispravnosti same mreže već je vrlo koristan pro kreiranju mnogih ovakvih konstrukcija.
Ova funckija je monotona, zato koristimo nula-jedan princip kao kontrapozitiv.
Konstrukcija sortirajućih mreža
Razni algoritim postoje za nastajanje jednostavnih ali efikasnih mreža dubine O(log2 n). Često se koriste u praksi. Teorijski je moguće konstruisati ove mreže sa logaritamskom dubinom, koristeći AKS mrežu. Iako je bitno teorijsko otkriće, ASK mreža ima malu ili nikakvu primenu zbog linearne konstante iza O notacije koja je veličine mnogo, mnogo hiljada. Postoji I pojednostavljena verzija AKS-a, koja naglašava da su konstante koje su dobijene za granicu dubine neodgovarajuće I da nemaju praktični značaj. Još jedna metoda konstrukcije sortirajuće mreže je otkrivena za O(n log n) ali iako ima manju konstantu od AKS-a, baš zbog O(n log n) složenosti ne može da efikasno ima paralelnu implementaciju.
Optimalne sortirajuće mreže
One mogu biti optimalno konstruisane za fiksirane unose odredjene n veličine, sa minimalnom dubinom ili minimalnom veličinom (brojem komparatora). One se mogu koristiti za povećanje performance većih sortirajućih mreža. Ova tabela prikazuje poznate rezultate optimizacije.
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Dubina | 0 | 1 | 3 | 3 | 5 | 5 | 6 | 6 | 7 | 7 | 8 | 8 | 9 | 9 | 9 | 9 |
Veličina, gornja granica | 0 | 1 | 3 | 5 | 9 | 12 | 16 | 19 | 25 | 29 | 35 | 39 | 45 | 51 | 56 | 60 |
Veličina, donja granica, ako je različita | 33 | 37 | 41 | 45 | 49 | 53 |
Prvih šesnaest dubinski- optimalnih mreža su navedene u Art of Computer Programming, koju je napisao Knut. Iako je optimalnost prvih osam dokazana još 60-ih godina, optimalnost poslednjih šest je pokazana tek 2014. godine (deveti I desti slučaj su dokazani 1991.) .
Za izradu optimalnih sortirajućih mreža su se čak koristili I genetski algoritmi. Knut kaže da su slučajevi za n=9 i n=11 zasnovani na toj metodi.
Reference
- ^ US 3029413, O'Connor, Daniel G. & Nelson, "Sorting system with n-line sorting switch", published 10. 4. 1962
- ^ Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). „GPU Computing”. Proceedings of the IEEE. 96 (5): 879. doi:10.1109/JPROC.2008.917757.
- ^ Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Second изд.). Addison–Wesley. стр. 219—247. ISBN 978-0-201-89685-5.