Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
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
Šaltiniai
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu , mobilusis, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris