Išplėstinė paieška
 
 
 
Pradžia>Matematika>Lygiagretusis spartusis rūšiavimo algoritmas
   
   
   
naudingas 0 / nenaudingas 0

Lygiagretusis spartusis rūšiavimo algoritmas

  
 
 
12345
Aprašymas

Nuoseklus spartusis rūšiavimo algoritmas. Algoritmo sudėtingumo įvertinimas. Lygiagretus spartusis rūšiavimo algoritmas. Duomenų keliavimo tarp keturių procesorių lyginis-nelyginis rūšiavimo algoritmo etape schema. Rezultatai "rs" klasteryje.

Ištrauka

Š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 surušiuota, priešingu atveju ir poaibį rušiuojame sparčiuoju algoritmu. Dažnai rekursiją 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 algoritmu.
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ų. ...

Rašto darbo duomenys
Tinklalapyje paskelbta2007-03-29
DalykasMatematikos kursinis darbas
KategorijaMatematika
TipasKursiniai darbai
Apimtis7 puslapiai 
Literatūros šaltiniai2
Dydis126 KB
AutoriusDarius
Viso autoriaus darbų1 darbas
Metai2007 m
Klasė/kursas3
Mokytojas/Dėstytojasprof. R. Čiegis
Švietimo institucijaVilniaus Gedimino Technikos Universitetas
FakultetasFundamentinių mokslų fakultetas
Failo pavadinimasMicrosoft Word Lygiagretusis spartusis rusiavimo algoritmas [speros.lt].doc
 

Panašūs darbai

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
  • Kursiniai darbai
  • 7 puslapiai 
  • Vilniaus Gedimino Technikos Universitetas / 3 Klasė/kursas
  • prof. R. Čiegis
  • 2007 m
Ar šis darbas buvo naudingas?
Taip
Ne
0
0
Pasidalink su draugais
Pranešk apie klaidą