Algoritmų sudarymas ir analizė

KAUNO TECHNOLOGIJOS UNIVERSITETAS INFORMATIKOS FAKULTETAS ALGORITMŲ SUDARYMAS IR ANALIZĖ LABORATORINIS DARBAS NR. 1 Varianto nr. 11 Atliko: Priėmė: Vaidas Astrovas 2009.04.09 KAUNAS 2021 1) Laboratorinio darbo užduotis ir variantas Pateiktos užduoties variantas - 11. Užduotyje buvo reikalaujama suprogramuoti tris rikiavimo algoritmus su dviem skirtingom duomenų struktūrom – su masyvais ir dinaminiais sąrašais. Pateikta programa turi būti sukompiliuota ir veikianti. Ją turi būti įmanoma paleisti nediegiant jokios papildomos programinės įrangos. Privaloma laikytis įvedimo ir išvedimo duomenų formatų, nurodytų kartu su laboratorinio darbo užduotimi. Turi būti galimybė generuoti atsitiktines duomenų imtis. Programa turi atspausdinti algoritmo atlikimo laiką ir atliktų operacijų kiekį. Užduotyje duoti algoritmai buvo: rūšiavimas burbulu (Bubble Sort), greitasis rūšiavimas (Quick Sort) ir rūšiavimo algoritmas “Radix Sort”. 2) Algoritmų analizė ir teorinis įvertinimas Bubble Sort algoritmas Burbulo metodas - vienas iš paprasčiausių, bet nelabai efektyvių rikiavimo algoritmų. Algoritmo principas – nuosekliai iš eilės peržiūrėti gretimų elementų poras, prireikus elementus sukeisti, perkeliant mažesnį arčiau pradžios. Tokiu būdu per pirmą iteraciją mažiausias elementas perkeliamas į pirmą poziciją, vėliau tas pats principas taikomas posekiui be pirmo elemento ir t.t. Algoritmo veikimo principas primena virimo procesą, kai oro burbulai kyla į paviršių, dėl to jis ir vadinamas burbulo metodu. Burbulo algoritmas N elementų masyvo rikiavimui naudoja apie N²/2 lyginimų ir N²/2 keitimų vietomis, tiek laukiamu, tiek ir blogiausiu atveju. Algoritmas nenaudoja papildomos atminties. Quick Sort algoritmas Algoritmas naudojasi „skaldyk ir valdyk“ paradigma. Pagrindinė idėja – išskaidžius duomenų seką į dvi dalis, kad vienoje dalyje visi elementai būtų mažesni už kitos dalies elementus, šias dvi dalis galima rikiuoti nepriklausomai viena nuo kitos. Tai daroma rekursiškai. Elementas, atskiriantis dalis – slenkstis. Algoritmas yra nestabilus. Geriausiai veikia, kai kiekvienąkart slenkstis skaido duomenis po lygiai. Šiuo atveju algoritmo sudėtingumas yra O(N log N), tačiau esant „blogiems“ duomenims, algoritmo sudėtingumas gali siekti O(N2). Radix Sort algoritmas Šis algoritmas taip pat remiasi „skaldyk ir valdyk“ paradigma. Pirmiausia, duomenys yra sugrupuojami pagal dešinįjį skaitmenį ir eilės tvarka surašomi atgal į masyvą. Tada imamas kitas skaitmuo ir daroma tas pats. Viskas vyksta tiek kartų, kiek skaitmenų turi didžiausias duomenyse esantis skaitmuo. Algoritmas stabilus ir labai greitas, sudėtingumas – O(N·k) (k – rakto ilgis). 3) Eksperimentų rezultatai Algoritmo „Bubble Sort“ vykdymo laikas(sek.) masyve ir sąraše   10000 20000 30000 40000 50000 Masyve 0,75 3,078 6,953 12,359 19,375 Sąraše 1,594 6,406 17,563 26,125 41,735 Algoritmų „Quick Sort“ ir „Radix Sort“ vykdymo laikas(sek.) masyve   500000 1000000 1500000 2000000 2500000 3000000 QuickSort 0,219 0,485 0,765 1,031 1,313 1,594 RadixSort 0,287 0,578 0,86 1,156 1,438 1,735 Algoritmų „Quick Sort“ ir „Radix Sort“ vykdymo laikas(sek.) sąraše   500000 1000000 1500000 2000000 2500000 3000000 QuickSort 0,36 0,813 1,282 1,766 2,312 2,75 RadixSort 0,297 0,64 0,953 1,281 1,625 1,953 4) Išvados Pažvelgus į algoritmų darbo grafikus, galima pastebėti, jog algoritmai greičiau susitvarko su masyvais, nei su dinaminiais sąrašais. Bet kuriuo atveju, Buble Sort algoritmas dirbo lėčiausiai ir naudojo daugiausiai darbinės atminties. Dėl darbinės atminties trūkumo nebuvo galima išbandyti šio algoritmo su didesnėmis imtimis ir palyginti su kitais algoritmais, nors galima daryti prielaidą, jog bandymų rezultatai nebūtų jam palankūs. Dirbant masyve greičiausiai duomenis surikiavo Radix Sort algoritmas, tačiau vertėtų pastebėti, jog Radix Sort algoritmo darbo trukmė priklauso ir nuo elementų skilčių skaičiaus, tad su mažiau skilčių turinčiais skaičiais, šis algoritmas susidoroja greičiau. Tuo tarpu Quick Sort algoritmo darbo laikas priklauso nuo elementų skaičiaus. 5) Programos išeities tekstai Main.h //--------------------------------------------------------------------------- #ifndef MainH #define MainH //--------------------------------------------------------------------------- #include

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!