Algoritmi un datu struktūras "Šķirošana ar Šella metodi (Shell 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 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.

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ī Šella (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 Šella 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.