Rēzeknes Augstskola
Inženieru fakultāte
Datorzinātņu un matemātikas katedra
Bubble Sort šķirošana
Autors
Dienas nodaļas
Inženiera programmētāja specialitātes
2.kursa studente
*********
************
Docētājs
*********. ________________ *************
Rēzekne 2006
Uzdevuma apraksts
Uzdevumu var nosacīti iedalīt vairākās daļās:
1.uzzīmēt BubbleSort blokshēmu;
2.uzrakstīt C++ funkciju, kas realizē BubbleSort 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 trīs grafikus, kas atspoguļo nepieciešamā laika atkarību no masīva izmēra.
Tā kā laiks, kas nepieciešams šķirošanai, ir jāmēra milisekundēs, izmantošu C++ iebūvēto bibliotēku <time.h> un tās iespējas, ko sniedz clock(), clock_t. Tā kā ar šo funkciju palīdzību iespējams izmērīt procesora tikšķu skaitu, var iegūt šķirošanai nepieciešamo laiku, atņemot no beigu vērtības sākuma datus. Tā kā procesora tikšķi tiek pielīdzināti milisekundēm un ir praktiski vienādi ar tām, varu uzskatīt, ka tiek mērīts eksperimenta laiks milisekundēs.
Nepieciešams izveidot funkciju, kas, ņemot par pamatu dinamisko masīvu un elementu skaitu tajā, veiks šķirošanu pēc burbuļa metodes.
Nepieciešams arī izveidot funkciju, kas izskaitļos katrai operācijai nepieciešamo laiku. Tā kā šķirošana ar burbuļa metodi tika definēta iepriekš, es to droši varu izsaukt no patreizējās laika mērīšanas funkcijas.
Nepieciešams 10 reizes izmērīt šķirošanas laiku trīs dažādas sakārtotības pakāpes masīviem, turklāt katrreiz palielinot to izmērus. Eksperimentālā ceļā noskaidroju, ka minimālais masīva elementu skaits, ko šķirojot, programma var mērīt laiku, ir aptuveni 800, bet, lai iegūtu skaidrākus un vienkāršākus rezultātus, par pirmo izmēru pieņemšu 1000. Pēc katra šķirošanas bloka palielināšu šo izmēru par 1000, līdz ar to beidzamais masīvs saturēs 10000 elementus.
Eksperimentu jāizpilda vismaz piecas reizes, lai iegūtu ticamus rezultātus.
Iegūtos rezultātus jāatspoguļo grafikā, kas parādīs masīva šķirošanas laika atkarību no masīva izmēra.
Īss blokshēmas apraksts: blokā 2 tiek funkcijai padots masīvs, kas jāšķiro, un masīva elementu skaits. Pēc tam tiek organizēts ieliktais cikls, kurā blokā 5 notiek masīva elementu salīdzināšana, blokos 6-8 notiek elementu apmaiņa vietām gadījumā, ja iepriekšējais elements ir lielāks par nākošo. Process turpinās, līdz vairs nav elementu, ko mainīt vietām. Izmantotie apzīmējumi: n-masīva izmērs; array[n]-masīvs, ar kuru tiks veiktas manipulācijas; temp-pagaidu vērtība, kurā tiek uzglabātas elementu vērtības apmaiņas procesā; i,j – mainīgie indeksācijai.
Programmas listings
# include <time.h>
# include <iostream.h>
# include <conio.h>
# include <stdlib.h>
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;
} } } }
//tā kā es jau nodefinēju šķirošanas funkciju, es varu atļauties viņu izmantot citā funkcijā
int time (int n, int array[])
{
double ticks; //tas ir, tikšķi
clock_t start, finish;
start = clock(); //ieslēdzam skaitītāju
bubblesort (n, array);
finish = clock(); //izslēdzam
ticks=finish-start; //atņemam un iegūstam patērēto laiku
return ticks;
}
void main () {
int i,j,k=1000; //k=1000 sākotnējais masīva izmērs - 1000 elementi
int a=0,b=0,c=0;
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
cout<<endl<<"Videeji sakaartots masiivs: ";
a+=time (k,array);
cout<<"Izmeers: "<<k<<" Laiks: "<<time (k, array);
cout<<endl<<"PIlniigi sakaartots masiivs: ";
b+=time(k,array);
//šeit jau ņemts iepriekšējais masīvs, kas ir jau sakārtots
cout<<"Izmeers: "<<k<<" Laiks: "<<time (k, array);
for (i=(k-1); i=0; i--) array[i]=i;
cout<<endl<<"Pilniigi nesakaartots masiivs: ";
c+=time (k,array);
cout<<"Izmeers: "<<k<<" Laiks: "<<time (k, array);
delete []array;
k=k+1000;
cout<<endl;
}
while (k<11000);
cout<<endl<<"Kopaa aiznjeema laika videeji sakaartota masiiva shkjiroshana: "<<a;
cout<<endl<<"Kopaa aiznjeema laika pilniigi sakaartota masiiva shkjiroshana: "<<b;
cout<<endl<<"Kopaa aiznjeema laika pilniigi nesakaartota masiiva shkjiroshana: "<<c;
getch();
}
1.attēls
Izdarot eksperimentu piecas reizes un aprēķinot vidējos rezultātus, es izveidoju šādu grafiku (1.att.). Līnijas atrodas tuvu viena otrai, kas varētu būt izskaidrojams ar ne pārāk lielajiem masīvu izmēriem (ja es būtu ņēmusi ievērojami lielākus masīvus, atšķirība šķirošanas laikā būtu ievērojami krasāka). Eksperimenta rezultātu arī ļoti ietekmēja mana datora konfigurācija (AMD Athlon 1,49 GHz, 192 Mb RAM). Kā var redzēt no grafika, šķirošana ar burbuļa metodi veido nelineāru grafiku, bet gan kvadrātiskas funkcijas grafiks. Jo lielāks elementu skaits masīvos, jo skaidrāk redzama atšķirība starp šķirošanas laikiem. Tātad šķirošana ar burbuļa metodi varētu būt efektīva tikai nelieliem masīviem, bet apjomīgu masīvu šķirošanai būtu jāizmanto kāda cita metode.
