Sortiranje "par-nepar"
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 уреди
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 уреди
- ^ Phillips, Malcolm. „Array Sorting”. Homepages.ihug.co.nz. Архивирано из оригинала 28. 10. 2011. г. Приступљено 3. 8. 2011.
- ^ 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).
- ^ 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
- ^ Robert Sedgewick (2003). Algorithms in Java, Parts 1-4 (3rd изд.). Addison-Wesley Professional. стр. 454—464. ISBN 978-0-201-36120-9.
- ^ Allen Kent & Williams, James G. (1993). Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. стр. 33—38. ISBN 978-0-8247-2282-1.
- ^ Škarić, Milan. Uvod u programiranje. Beograd: Mikro knjiga. „Implementacija Parnog neparnog sortiranja u programskom jeziku c”
Literatura уреди
- Allen Kent & Williams, James G. (1993). Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. стр. 33—38. ISBN 978-0-8247-2282-1.
- Sedgewick, Robert (2003). Algorithms in Java, Parts 1-4 (3rd изд.). Addison-Wesley Professional. стр. 454—464. ISBN 978-0-201-36120-9.
- Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати овде Архивирано на сајту Wayback Machine (18. октобар 2016)
- Algoritmi i strukture podataka - Milo Tomašević
- Uvod u programiranje - Milan Škarić