Rēzeknes Augstskola
Inženieru fakultāte
Datorzinātņu un matemātikas katedra
ALGORITMI UN DATU STRUKTŪRAS
2.mājas darbs
Šķirošana ar izvēli (selection sort)
Autors
Dienas nodaļas
Inženiera programmētāja specialitātes
********
*********
St. apliecības ************
Docētājs
Lekt.Mg.sc.ing. ________________ **********
Rēzekne 2006
Uzdevuma apraksts
Uzdevumu var nosacīti iedalīt vairākās daļās:
1. uzzīmēt šķirošanas ar izvēli funkcijas blokshēmu;
2. uzrakstīt C++ funkciju, kas realizē šķirošanas ar izvēli algoritmu veselu skaitļu masīvam;
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.
Eksperimenta plāns
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.
Šķirošanas ar izvēli funkcijas blokshēma
Programmas listings
# include <time.h>
# include <iostream.h>
# include <conio.h>
# include <stdlib.h>
# include <fstream>
# include <iomanip.h>
void selectionsort (int n, int array[]) //n – masīva izmērs, array[] – pats masīvs
{ int temp, min;
for (int i=0; i<(n-1); i++)
{
min = i; //patreizējais minimālais elements
//meklējam globālo minimumu
for (int j=i+1; j<n; j++)
{
if (array[min]>array[j])
{
min=j; //jaunais minimālais elements
}
}
temp=array[i]; //apmainām vietām
array[i]=array[min];
array[min]=temp;
}
}
void bubblesort (int n, int array[]) //n – masīva izmērs, array[] – pats masīvs
{ int temp;
for (int i=(n-1); i>=1; i–)
{
for (int j=0; j<i; j++)
{
if (array[j]>array[j+1]) //salīdzinām, ja vajag – mainām vietām
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
} } } }
int time (int n, int array[])
{
double ticks; //tas ir, tikšķi
clock_t start, finish;
start = clock(); //ieslēdzam skaitītāju
selectionsort (n, array);
finish = clock(); //izslēdzam
ticks=finish-start; //atņemam un iegūstam patērēto laiku
return ticks;
}
void main () {
ofstream output;
int i,j,k=1000; //k=1000 sākotnējais masīva izmērs – 1000 elementi
int a=0,b=0,c=0,a1=0,b1=0,c1=0;
output.open (“output.txt”);
output<<setw(20)<<left<<“Izmērs: “<<setw(20)<<“Vidēji sakārtots: “<<setw(20)<<“Pilnīgi sakārtots:”
<<setw(20)<<“Pilnīgi nesakārtots: “<<endl;
output<<“***************************************************************************”<<endl;
do {
int *array=new int[k]; //jauns dinamiskais masīvs
randomize();
for (i=0; i<k; i++)
array[i]=random(101); //nejauši ģenerēts masīvs
a1=time(k,array);
output<<setw(20)<<k<<setw(20)<<a1;
a+=a1;
b1=time(k,array);
output<<setw(20)<<b1;
b+=b1;
//šeit jau ņemts iepriekšējais masīvs, kas ir jau sakārtots
for (i=(k-1); i=0; i–) array[i]=i;
c1 = time (k,array);
output<<setw(20)<<c1<<endl;
c+=c1;
delete []array;
k=k+1000;
}
while (k<11000);
output<<“***************************************************************************”<<endl;
output<<setw(20)<<“Kopā: “<<setw(20)<<a<<setw(20)<<b<<setw(20)<<c;
output.close();
cout<<“Viss, pabeidzaam – spied jebko un apskaties rezultātus failaa.”;
getch();
}
Iegūtie rezultāti un secinājumi
Šādus rezultātus es ieguvu, šķirojot ar burbuļa metodi (apkopotie gala rezultāti, vidējā vērtība, kas iegūta piecos eksperimentos):
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
vid 10,2 20,2 58 94,2 162 214,2 306,4 388,2 506,4 603
min 9 26 50 90 146,2 212,6 294,6 378,2 484,8 596,8
max 10 30 58 98,4 152,4 238,2 322,6 422,6 532,6 635
Un šādi bija rezultāti, šķirojot ar izvēles metodi (arī apkopoti jau vidējie rezultāti, ņemot vērā piecus eksperimentus):
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
vid 6,2 12 30 70,2 98 152,2 214,4 272,4 328,6 404,4
min 4,6 14 36 68,4 94 140 190,2 268,2 324 392,4
max 10 20 42 78,2 100,2 156,4 220,2 260,4 337 430,6
Attēlojot iegūtos rezultātus grafikos, ieguvu:
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.
Grafikos līnijas atrodas ļoti tuvu viena otrai, jo rezultāti bieži ir ļoti tuvi. Es domāju, ka šo problēmu varētu novērst, ja daudzkārt palielinātu šķirojamo masīvu apmēru robežas, bet, mēģinot tā izdarīt, es saskāros ar jaunu problēmu – programmas izpilde prasīja ārkārtīgi daudz laika. Tā, piemēram, pamainot sākotnējā masīva izmēru uz 10000 un katrā iterācijā palielinot to par 1000, un par beigu nosacījumu pieņemot masīvu ar izmēru 100000, programma darbojās apmēram 15 minūtes (šķirošanas laiks, masīva elementu ģenerēšanas laiks, masīvu radīšana, izdzēšana, rezultātu izvade).
Lai gan viens no nosacījumiem uzdevuma izpildei bija ievietot iepriekš izveidotajā programmā tikai jaunu funkciju šķirošanai, un nemainīt sākotnējo kodu, es tomēr nolēmu to pilnveidot. Iemesli: nepārskatāma rezultātu izvade un neērta to apstrāde. Pārnesot datu izvadi no ekrāna uz failu, es ieguvu arī rezultātu kopēšanas iespējas.
Šķirošanu ar izvēles metodi varētu vēl vairāk paātrināt, ja katrā iterācijā meklētu ne tikai masīva minimālo elementu, bet arī maksimālo, un attiecīgi izvietotu šos abus elementus ( tā saucamais Shaker sort ). Bet dažos literatūras avotos (piemēram, http://wikipedia.org) tāds šķirošanas veids tiek pieskaitīts šķirošanas ar burbuļa metodi variācijām, tāpēc es to neizmantoju savā programmā.
Sandra Lobazova
17.03.2006.