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 (eng. 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 (eng. 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. pp. 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. pp. 33-38. ISBN 978-0-8247-2282-1. 

Literatura[уреди]