Lygiagretusis spartusis rūšiavimo algoritmas

VILNIAUS GEDIMINO TECHNIKOS UNIVERSITETAS Matematinio modeliavimo katedra Lygiagretusis spartusis rūšiavimo algoritmas Atliko: TM-4/2 gr.stud.Darius Ciūnys Tikrino: prof. R. Čiegis Vilnius 2007 Nuoseklus spartusis rušiavimo algoritmas Šis algoritmas labai plačiai naudojamas daugelyje taikomųjų programų Paro-dysime, kad jo vidutinis sudėtingumas yra O(N log N), o realizacija yra paprasta ir nereikia papildomos atminties rūšiuojamam elementų saugojimui. Todėl jis ir va-dinamas sparčiuoju algoritmu (angl. quick sort). Spartusis rušiavimo algoritmas yra sukonstruotas remiantis skaldyk ir valdyk metodu. Paaiškinsime, kaip realizuojami trys pagrindiniai jo etapai. Uzdavinio skaidymas. Visą rušiuojama, aibę dalijame į du poaibius. Tuo tikslu parenkame pagrindinį elementą (aij (angl. pivot), tada pirmajam poaibiui priskiriame elementus mažesnius už aij, o antrajam poaibiui - nemažesnius už pagrindinį elementą. Dalinio uždavinio sprendimas. Jei poaibį sudaro vienas elementas, tai jis jau su-rušiuota, priešingu atveju ir poaibį rušiuojame sparčiuoju algoritmu. Dažnai rekur-siją užbaigiame anksčiau, pasirenkame nedidelį skaicių M ir jei poaibio elementų skaičius yra nedidesnis už M, tai poaibį surušiuojame kuriuo nors paprastu algo­ritmu. Viso uždavinio sprendinio radimas. Kadangi visi pirmojo poaibio elementai yra mažesni už antrojo poaibio elementus, tai išsprendę dalinius uždavinius mes surušiuojame ir visą, aibę. Taigi šiame etape nereikia atlikti jokių papildomų veiksmų. Spartusis rušiavimo algoritmas QuickSort (l, r) begin (1) if (K(r-M)){ (2) Partition (l, r, INew, rNew ); (3) QuickSort (l, rNew ); (4) QuickSort (INew, r ); } else (5) if (l v ) j = j - 1; (6) if (Uj){ (7) if (i 2: L(1)=0, L(2)=1. Pritaikę rekurentinę lygybę N - 2 kartus, apskaičiuojame elementų lyginimų skaicių Taigi blogiausiu atveju spartusis rūšiavimo algoritmas yra toks pat lėtas, kaip ir paprasti rūšiavimo algoritmai (SelectionSort, BubleSort, InsertionSort). Ypač netikėta yra tai, kad tokį blogą rezultatą gauname, pavyzdžiui, kai rūšiuojame jau surūšiuotą aibę, o pagrindiu aibės elementu renkamės pirmąjį elementą. Dabar nagrinėkime geriausią atvejį, kai kiekviename žingsnyje pavyksta aibę padalinti dvi lygias. Kad skaičiavimo rezultatai būtų paprstesni, imkime N=2m. Tada gauname tokį saryšį, susiejantį elementų lyginimų skaičius: Pritaikę šią lygybę m-1 kartą, apskaičiuojame elementų lyginimų skaičių Taigi geriausiu atveju sparčiojo rūšiavimo algoritmo skaičiavimų apimtis yra optimali. Spartusis rūšiavimo algoritmas tapo tokiu populiariu todėl, kad vidutiniu atveju skaičiavimų apimtis nedaug skiriasi nuo geriausio atvejo. Jeigu turime N elementų, tai viso gali būti N! skirtingų jų pasiskirstymų. Tarkime, kad jie visi yra vienodai tikėtini. Skaičiuodami vidutinį elementų lyginimų skaičių, atsižvelgiame į tai, kad uždavinio skaidymo etape atliekame N-1 lyginimą, o po to su vienoda tikimybe gali tekti rūšiuoti N-1 skirtingus dalinius poaibius, todėl Šią lygtį galime suprastinti: Imdami N-1 elementą turime lygtį Iš šių dviejų lygybių gauname tiesinę skirtumų lygtį , kurią galime užrašyti ir simetrine forma: . Užrašę tokias lygtis visoms N reikšmėms ir jas sudėję, bei atsižvelgią į tai, kad Lv(1)=0, gauname lygybę . Nesunku įrodyti, kad harmoninės eilutės dalinė suma tenkina nelygybę: , todėl . Atsižvelgę į lygybę gauname sparčiojo rūšiavimo algoritmo vidutinį elemtų lyginimų skaičių kuris rodo, kad vidutinis atvejis yra 40 procentų blogesnis už geriausią atvejį. Lygiagretus spartusis rušiavimo algoritmas Lygiagretus rūšiavimo algoritmas tam tikrais atvejais yra optimalus. Jame naudosime tiek greitojo rūšiavimo nuosekliuosius algoritmus, tiek lygiagretųjį lyginį-nelyginį rūšiavimo algoritmą. Elementus skirstome blokais p procesoriams. Iš pradžių kiekvienas procesorius savo turimus elementus kuriuo greitojo rūšiavimo algoritmu. Šios dalies skaičiavimo sąnaudos yra Tlokalus=O(m log m). Vėliau procesoriai įvykdo p blokinio lyginio-nelyginio rūšiavimo algoritmo žingsnių.kiekvieno tokio žigsnio metu du procesoriai pasikeičia savo elementais ir sujungia du jau surūšiuotus sąrašus. Kairysis procesorius pasilieka m mažiausių bendro sąrašo elementų, o dešinysis m didžiausių elementų. Šios algoritmo dalies skaičiavimo sąnaudos yra Tsujungimas=pO(m)=O(n). Duomenų pasikeitimo sąnaudos irgi įvertinamos formule Tkomunikacija=pO(m)=O(n). Todėl visos lygiagrečiojo algoritmo realizavimo sąnaudos yra Tp= Tlokalus+Tsujungimas+Tkomunikacija= Tada lygiagrečiojo algoritmo spartinimo koeficientasyra ir Sp≈p, jei elementų skaičius, tenkantis vienam procesoriui, yra tikrai didelis. Lygiagrečiojo algoritmo efektyvumo koeficientas yra todėl algoritmo realizacijos sąnaudos yra optimalios, p= O(log n), t.y. efektyviai galime naudoti nedaug procesorių. Algoritmo izoefektyvumo funkcija yra Θ(p2p), todėl, didindami procesorių skaičių ir siekdami išlaikyti tokį patį algoritmo efektyvumą, aibės elemtų skaičių turime didinti eksponentiniu greičiu. Taigi algoritmo išplečiamumo savybė nėra gera. Duomenų keliavimo tarp keturių procesorių lyginis-nelyginis rūšiavimo algoritmo etape schema: for(i=0;i

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!