Rēzeknes Augstskola
Inženieru fakultāte
Datorzinātņu un matemātikas katedra
Šķirošana ar Šella metodi (Shell 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 ievietošanu 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 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.
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 4 – 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.
Šķ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}.
Programmas kods
# include <time.h>
# include <iostream.h>
# include <conio.h>
# include <stdlib.h>
# include <fstream>
# include <iomanip.h>
using namespace std;
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;
} } } }
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 insertionsort (int n, int array[]) //n - masīva izmērs, array[] - pats masīvs
{
int i,j,temp;
for (i=1; i<n; i++)
{
temp=array[i];
for (j=i-1; j>=0&&array[j]>temp; j--)
{
array[j+1]=array[j];
}
array[j+1]=temp;
} }
void shellsort(int n, int array[])
{ int i, j, k, h; int v;
int l=5;
int incs[5] = { 7,5,4,3,1 };
for ( k = 0; k < 5; k++)
for (h = incs[k], i = l+h; i <= n; i++)
{
v = array[i];
j = i;
while (j > h && array[j-h] > v)
{ array[j] = array[j-h]; j -= h; }
array[j] = v;
} }
int time (int n, int array[], int number)
{
double ticks; //tas ir, tikšķi
clock_t start, finish;
start = clock(); //ieslēdzam skaitītāju
if (number == 1) bubblesort(n,array);
else if (number==2) selectionsort(n,array);
else if (number==3) insertionsort(n,array);
else shellsort(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;
double rez[10][3];
ofstream output;
output.open ("rezultati.txt");
output<<setw(20)<<"Pilnīgi sak."<<setw(20)<<"Vidēji sak."<<setw(20)<<"Pinīgi nes.";
for (int f=1; f<5; f++) //visas šķirošanas metodes
{
output<<endl<<"-----------------------------------------------------------------------";
if (f==1) output<<endl<<"Bubble Sort"<<endl;
else if (f==2) output<<endl<<"Selection Sort"<<endl;
else if (f==3) output<<endl<<"Insertion Sort"<<endl;
else output<<endl<<"Shell Sort"<<endl;
for (int g=0; g<10; g++) for (int z=0; z<3; z++) rez[g][z]=0;
for (int a=0; a<5; a++)
//laižam cauri šķirošanu 5 reizes pa 10 augošiem masīvu izmēriem
{
k=10000; //sākotnējais masīva izmērs 10 000 elementi
int count=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
rez[count][1] += time(k, array, f);
rez[count][0] += time(k, array, f); //pilnīgi sakārtots masīvs
for (i=(k-1); i=0; i--) array[i]=i;
rez[count][2] += time(k, array, f); //masīvs pretējā secībā
k=k+1000;
count++;
delete []array;
}
while (k<20000); //beidzam, kad masīva izmērs sasniedz 19 000 elementus
}
for (int g=0; g<10; g++) {
for (int z=0; z<3; z++) { output<<setw(20)<<rez[g][z]/5; }
output<<endl; }
}
output.close();
cout<<"Results are ready, press any key to quit.";
getch();
}
Pilnīgi sak. Vidēji sak. Pinīgi nes.
-----------------------------------------------------------------------
Bubble Sort
641 1289.8 662.6
781 1488.4 785.2
909.4 1700.2 931.4
1029.2 1959 1051.6
1285.8 2485.6 1275.6
1488.2 2742.2 1480.4
1682.4 3138.2 1676.6
1849 3470.6 1828.4
2107 3877.6 2113
2317.6 4312.2 2287.2
-----------------------------------------------------------------------
Selection Sort
395 392.4 396.2
483 490.8 482.2
575 574.8 577
680.8 683 675
775 787.2 781.2
909.2 913.4 887.2
1005.4 1007.6 1025.2
1151.6 1162 1167.8
1309.6 1334 1310
1464.2 1460 1466.2
-----------------------------------------------------------------------
Insertion Sort
0 378.4 0
0 466.6 0
0 555 0
0 675 0
0 759 0
2 861 2
0 972 0
0 1093 0
2 1226 0
0 1384 0
-----------------------------------------------------------------------
Shell Sort
0 76.2 2
2 84.2 0
2 96.2 2
0 118.2 0
0 124.2 0
0 164.2 6
2 160.2 0
8 188.4 2
2 232.2 4
2 228.2 2
No visām apskatītajām iepriekš metodēm Šella metode izrādījās visefektīgākā, par ievērojamiem lielumiem apsteidzot šķirošanu ar ievietošanas metodi. Turklāt šķirošanas ar Šella metodi rezultāti radītais grafiks ievērojami atšķiras no pārējo šķirošanas metožu grafikiem, kas visi bija lielākā vai mazākā ziņā eksponenciāli grafiki. Līdz ar to var izdarīt secinājumu, ka šķirošanas ar Šella metodi ātrdarbības laiku ir ļoti grūti paredzēt. Acīmredzot šķirošanas rezultātus ļoti spēcīgi ietekmē izvēlētie soļi. Spriežot pēc grafika, manis izvēlētos soļus {7,5,4,3,1} varētu vēl uzlabot un atrast labāku variantu.
Sandra Lobazova
19.05.2006.
