Par-nepar sortiranje

Из Википедије, слободне енциклопедије
Par-nepar sortiranje
Odd even sort animation.gif
Namena sortiranje
Struktura podataka Niz
Vremenska kompl. O(n²)

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]

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;
        }
    }
}

Reference[уреди]

  1. ^ Phillips, Malcolm. Sort Techniques „Array Sorting“ Приступљено 3. 8. 2011.. 
  2. ^ 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).
  3. ^ S. Lakshmivarahan, S. K. Dhall, and L. L. Miller (1984), Franz L. Alt and Marshall C. Yovits, ed., „Parallel Sorting Algorithms“, Advances in computers (Academic Press) 23: 295-351, ISBN 978-0-12-012123-6 
  4. ^ Robert Sedgewick (2003). Algorithms in Java, Parts 1-4 (3rd ed.). Addison-Wesley Professional. стр. 454-464. ISBN 978-0-201-36120-9. 
  5. ^ Allen Kent and James G. Williams (1993). Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. стр. 33-38. ISBN 978-0-8247-2282-1. 

Literatura[уреди]