Azərbaycan
Deutschland
Lietuva
ශ්රී ලංකාව
Türkiyə
Rikiavimo algoritmas algoritmas dėstantis duomenis tam tikra tvarka Algoritmo darbas priklauso nuo duomenų tvarkos apibr
Rikiavimo algoritmas
Rikiavimo algoritmas – algoritmas, dėstantis duomenis tam tikra tvarka. Algoritmo darbas priklauso nuo duomenų tvarkos apibrėžimo, duomenų struktūros, rikiuojamų, atminties panaudojimo rikiavimui, duomenų pateikimo vienalaikiškumo, eiliškumo, kitų veiksnių.
Nuo pat kompiuterių mokslo pradžios rikiavimo uždaviniai susilaukė daug tyrimų, pavyzdžiui, burbulo rikiavimo algoritmas buvo analizuojamas nuo 1956 m.
Skirstymas
Rikiavimo algoritmai gali būti skirstomi keliais būdais:
- Pagal naudojamą atmintį. Priklausomai nuo to, ar naudoja tik vidinę kompiuterio atmintį, ar jiems reikia ir išorinės, rikiavimo algoritmai skirstomi į vidinio rikiavimo ir . Taip pat algoritmus galima skirstyti ir pagal reikiamos atminties kiekį (nereikia visai; reikia tik rodyklėms; papildomai reikia tiek, kiek yra duomenų).
- Pagal stabilumą. Stabilūs algoritmai nekeičia lygių elementų tvarkos, o nestabilūs algoritmai to negarantuoja.
- Pagal sudėtingumą.
Lygiagretieji algoritmai
Naudojant daugiaprocesorinį kompiuterį ar paskirstytą kompiuterių tinklą galima pasiekti ir dar geresnių rezultatų. Geriausiu atveju pasiekiamas sudėtingumas O ((log N)²).
Rikiavimo algoritmų sudėtingumas
Dažnai greitam darbui su duomenimis būtina duomenis susirikiuoti, bet esant dideliems duomenų kiekiams labai svarbu ir paties rikiavimo algoritmo sudėtingumas – atlikimo greičio (arba tam tikrų, pasirinktų operacijų skaičiaus) priklausomybė nuo duomenų kiekio.
Algoritmų analizėje duomenų rikiavimo problema laikoma pačia svarbiausia, nes tai viena dažniausiai pasitaikančių operacijų programavime. Efektyvus rikiavimo algoritmo pasirinkimas gali turėti netgi lemiamą įtaką programos vykdymo spartai didėjant duomenų kiekiui.
Algoritmų sudėtingumų lentelė
| Algoritmas | Blogiausias | Tikėtinas | Geriausias | Pastabos (stabilumas, atmintis, išorinis/vidinis) |
|---|---|---|---|---|
| Skaitmeninis radixsort | O(2d N) | O(2d N) | O(2d N) | Tik skaitmeninėms teigiamoms duomenų reikšmėms, kur d yra skaitmenų sk. Reikalauja papildomos atminties |
| Greitojo rikiavimo (quicksort) | O(N²) | O(N log N) | O(N log N) | Beveik nenaudoja papildomos atminties |
| Kombinuotas | O(N log N) | O(N (log N)²) | ||
| Krūvos (heapsort) | O(N log N) | O(N log N) | O (N log N) | Nestabilus, nenaudoja papildomos atminties |
| Šelo (Shell sort) | O(N²) | O(N1,2) | O(N) | |
| Sąlajos (mergesort) | O(N log N) | O(N log N) | O(N log N) | Stabilus, naudoja papildomą atmintį. Tinka, kai iš karto galime nuskaityti nevisus duomenis į operatyvią atmintį |
| Burbulo (bubble) | O(N²) | O(N²) | O(N) | Nenaudoja papildomos atminties |
| Įterpimo (insertion) | O(N²) | O (N²) | O(N) | Stabilus |
| Išrinkimo (selection) | O(N²) | O(N²) | O(N²) |
Taip pat skaitykite
- Įvairūs rikiavimo algoritmai
- Klasifikavimo algoritmai
Šaltiniai
- Astrachan, Owen (2003-01-11). „Bubble sort: an archaeological algorithmic analysis“. ACM SIGCSE Bulletin. 35 (1): 1–5. doi:10.1145/792548.611918. ISSN 0097-8418.
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Rikiavimo algoritmas, Kas yra Rikiavimo algoritmas? Ką reiškia Rikiavimo algoritmas?
Rikiavimo algoritmas algoritmas destantis duomenis tam tikra tvarka Algoritmo darbas priklauso nuo duomenu tvarkos apibrezimo duomenu strukturos rikiuojamu atminties panaudojimo rikiavimui duomenu pateikimo vienalaikiskumo eiliskumo kitu veiksniu Salajos rikiavimo algoritmas Nuo pat kompiuteriu mokslo pradzios rikiavimo uzdaviniai susilauke daug tyrimu pavyzdziui burbulo rikiavimo algoritmas buvo analizuojamas nuo 1956 m SkirstymasRikiavimo algoritmai gali buti skirstomi keliais budais Pagal naudojama atmintį Priklausomai nuo to ar naudoja tik vidine kompiuterio atmintį ar jiems reikia ir isorines rikiavimo algoritmai skirstomi į vidinio rikiavimo ir Taip pat algoritmus galima skirstyti ir pagal reikiamos atminties kiekį nereikia visai reikia tik rodyklems papildomai reikia tiek kiek yra duomenu Pagal stabiluma Stabilus algoritmai nekeicia lygiu elementu tvarkos o nestabilus algoritmai to negarantuoja Pagal sudetinguma Lygiagretieji algoritmaiNaudojant daugiaprocesorinį kompiuterį ar paskirstyta kompiuteriu tinkla galima pasiekti ir dar geresniu rezultatu Geriausiu atveju pasiekiamas sudetingumas O log N Rikiavimo algoritmu sudetingumasDaznai greitam darbui su duomenimis butina duomenis susirikiuoti bet esant dideliems duomenu kiekiams labai svarbu ir paties rikiavimo algoritmo sudetingumas atlikimo greicio arba tam tikru pasirinktu operaciju skaiciaus priklausomybe nuo duomenu kiekio Algoritmu analizeje duomenu rikiavimo problema laikoma pacia svarbiausia nes tai viena dazniausiai pasitaikanciu operaciju programavime Efektyvus rikiavimo algoritmo pasirinkimas gali tureti netgi lemiama įtaka programos vykdymo spartai didejant duomenu kiekiui Algoritmu sudetingumu lentele Algoritmas Blogiausias Tiketinas Geriausias Pastabos stabilumas atmintis isorinis vidinis Skaitmeninis radixsort O 2d N O 2d N O 2d N Tik skaitmeninems teigiamoms duomenu reiksmems kur d yra skaitmenu sk Reikalauja papildomos atmintiesGreitojo rikiavimo quicksort O N O N log N O N log N Beveik nenaudoja papildomos atmintiesKombinuotas O N log N O N log N Kruvos heapsort O N log N O N log N O N log N Nestabilus nenaudoja papildomos atmintiesSelo Shell sort O N O N1 2 O N Salajos mergesort O N log N O N log N O N log N Stabilus naudoja papildoma atmintį Tinka kai is karto galime nuskaityti nevisus duomenis į operatyvia atmintįBurbulo bubble O N O N O N Nenaudoja papildomos atmintiesĮterpimo insertion O N O N O N StabilusIsrinkimo selection O N O N O N Taip pat skaitykiteĮvairus rikiavimo algoritmai Klasifikavimo algoritmaiSaltiniaiAstrachan Owen 2003 01 11 Bubble sort an archaeological algorithmic analysis ACM SIGCSE Bulletin 35 1 1 5 doi 10 1145 792548 611918 ISSN 0097 8418