Algoritmi un datu struktūras "Šķirošana ar Hoāra metodi (Quick Sort)" šķirošana C++

3. izveidot testēšanas programmu, kas ģenerēs masīvus, šķiros tos un salīdzinās šķirošanai nepieciešamo patērēto laiku (milisekundēs); šķirot un ģenerēt trīs dažāda veida masīvus: pilnīgi sakārtotu masīvu, vidēji sakārtotu masīvu un pilnīgi nesakārtotu masīvu;

4. uzzīmēt grafiku, kas atspoguļo nepieciešamā laika atkarību no masīva izmēra;

5. salīdzināt šķirošanas ar ievietošanu eksperimentu laikā iegūtos rezultātus ar šķirošanas ar burbuļa metodi, izvēles metodi, ievietošanas metodi, Šella metodi iegūtajiem rezultātiem, izdarīt secinājumus.

Datora, uz kura tika veikta šķirošana, tika pievienota papildus operatīvā atmiņa. Līdzšinējo 265 MB vietā tagad ir uzstādīti 768 MB.

Šķirošanai ar Šella metodi soļus izvēlējos, vairāk kārt mēģinot, līdz nonācu pie varianta {7,5,4,3,1}.

Lai pārbaudītu, kā uzlabojumi ietekmē šķirošanu ar iepriekšējām metodēm (masīvi ar tādiem pašiem izmēriem), es veicu šķirošanu ar burbuļa metodi (ar metodi, kas no visām iepriekš izskatītajām teorētiski patērē visvairāk laika šķirošanai) dinamiskajiem masīviem. Bubble sort vidēji rādīja laiku 0 tikai pirmajās 2 3 šķirošanas reizēs (t.i., ar masīva izmēriem 1000, 2000, 3000).

Lai pārbaudītu, kā uzlabojies šķirošanas laiks pārējām metodēm un lai noteiktu optimālo masīva sākuma izmēru, es veicu šķirošanu arī ar pārējām metodēm, tostarp arī Hoāra (protams, es vispirms ar elementāras programmas un nelielu masīvu palīdzību pārbaudīju, ka algoritms strādā korekti un masīvs tiek pareizi sašķirots, tikai tad ievietoju šķirošanas ar Hoāra metodi funkciju galvenajā programmā).

Šķirošana ar izvēles metodi nulles laiku rādīja pirmo divu masīvu šķirošanas laiku vietā. Šķirošana ar ievietošanas metodi uzrādīja interesantus rezultātus: vidēji sakārtotam masīvam un nesakārtotam masīvam, izņemot pirmo iterāciju, tika uzrādīts šķirošanas laiks, bet pilnīgi sakārtotam masīvam visās iterācijās tika uzrādīta nulle. Šķirošana ar Šella metodi arī uzrādīja tādus pašus rezultātus – pilnīgi sakārtotam masīvam šķirošanas laiks bija nulle.

Lai novērstu iespējamību, ka tā ir programmas koda kļūda, es vairāk kārt atkārtoju mēģinājumus ar visām četrām metodēm, turklāt šķirošanai ar burbuļa un izvēles metodēm tika uzrādīti visi trīs šķirošanai nepieciešamie laiki.

Pēc šiem eksperimentiem es nolēmu šķirošanu visām metodēm uzsākt ar 10’000 elementu lielu masīvu un veikt 10 reizes, katru reizi palielinot masīva izmēru par 1000.

Tā kā ir 3 dažādi masīvi (sašķirots, vidēji sašķirots, sašķirots pretējā secībā), un 10 masīvu izmēri, kā arī 4 šķirošanas metodes, tad rezultātu uzglabāšanai es izvēlējos divdimensiju matricu 10x3, un šādas matricas tika izveidotas 5 – katrai šķirošanas metodei pa vienai matricai.

Katra šķirošanas metode tiek veikta 5 reizes, katru no šīm 5 reizēm tiek kārtoti masīvi ar izmēru no 10’000 līdz 19’000 un rezultāti uzglabāti tabulā, piemēram, tabulas pirmās rindas pirmajai kolonnai šķirošanas ar vienu no metodēm nobeigumā būs visu 5 masīvu ar izmēru 10’000 vidējais šķirošanas laiks (cikliski uzglabājam summu un izdalām ar 5). Rezultātus uzglabāju failā, lai tos pēcāk varētu vieglāk apstrādāt.