Algoritmi un datu struktūras "Šķirošana ar izvēli (selection 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 izvēli eksperimentu laikā iegūtos rezultātus ar šķirošanas ar burbuļa metodi iegūtajiem rezultātiem, izdarīt secinājumus.

Pārveidot jau iepriekš radīto programmu šķirošanai ar burbuļa metodi, ievietojot tajā jaunu funkciju šķirošanai ar izvēles metodi, pamainīt galvenajā programmas daļā funkcijas izsaukšanas vietā burbuļa šķirošanu uz izvēles šķirošanu.

Tā kā rezultātu norakstīšana no ekrāna ir apgrūtinoša, nodrošināt rezultātu izvadi tabulas veidā failā.

Eksperimentu veikt uz datora ar tādu pašu konfigurāciju, kāda bija datoram, uz kura veica iepriekšējo eksperimentu (AMD Athlon 1,49 GHz, 192 Mb RAM).

Palaist programmu ar tādiem pašiem datiem, kā iepriekš šķirojot ar burbuļa metodi (tas ir, masīva izmērs no 1000 līdz 10000). Palaist programmu piecas reizes un saglabāt rezultātus.

Aprēķināt vidējo laiku, kas bija nepieciešams vidēji sašķirota, pilnīgi nesašķirota un pilnīgi sašķirota masīva šķirošanai.

Uzzīmēt grafiku, kas šiem trijiem masīvu veidiem parāda šķirošanas laika atkarību no masīva izmēriem.

Salīdzināt iegūtos rezultātus ar iepriekš iegūtajiem, kad tika šķirots ar burbuļa metodi. Izdarīt secinājumus.

void selectionsort (int n, int array[]) //n masīva izmērs, array[] pats masīvs

void bubblesort (int n, int array[]) //n masīva izmērs, array[] pats masīvs

Šādus rezultātus es ieguvu, šķirojot ar burbuļa metodi (apkopotie gala rezultāti, vidējā vērtība, kas iegūta piecos eksperimentos):

Un šādi bija rezultāti, šķirojot ar izvēles metodi (arī apkopoti jau vidējie rezultāti, ņemot vērā piecus eksperimentus):

Kā redzams ne tikai no grafikiem, bet arī jau no iegūto rezultātu apkopojumiem tabulās, šķirošana ar izvēles metodi ir daudz ātrāka nekā šķirošana ar burbuļa metodi. Ja salīdzina, piemēram, pilnīgi nesakārtota 5000 elementu liela masīva šķirošanu: šķirošana ar burbuļa metodi aizņēma 152,4 milisekundes, bet šķirošana ar izvēles metodi aizņēma tikai 100,2 milisekundes.