Rēzeknes Augstskola
Inženieru fakultāte
Datorzinātņu un matemātikas katedra
ALGORITMI UN DATU STRUKTŪRAS
Šķirošana ar Hoāra metodi (Quick Sort)
Autors
Dienas nodaļas
Inženiera programmētāja specialitātes
**************
***********
St. apliecības Nr.:**********
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 Hoāra metodi funkcijas blokshēmu;
2. uzrakstīt C++ funkciju, kas realizē šķirošanas ar Hoāra metodi 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, Šella metodi iegūtajiem rezultātiem, izdarīt secinājumus.
Eksperimenta plāns
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.
Šķ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}.
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ī Hoāra (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 Hoāra 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 10×3, un šādas matricas tika izveidotas 5 – 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.
Jau testēšanas posmā atklājās, ka šķirošanai ar Šella un Hoāra metodēm nepieciešama atsevišķa tikai šo divu metožu izpēte, jo tās abas šķiroja masīvus tik ātri, ka nebūtu adekvāti tās salīdzināt ar burbuļa, ievietošanas un izvēles šķirošanas metodēm. Līdz ar to pēc galvenās testēšanas procedūras es veicu vēl vienu – tikai šķirošanai ar Šella un Hoāra metodēm. Lai uzskatamāk saredzētu atšķirības, es palielināju masīvu izmērus. Šķirošanu uzsāku ar 100’000 elementu lielu masīvu (līdzšinējo 10’000 vietā) un beidzu ar 109’000 elementu lielu masīvu (līdzšinējo 19’000 vietā).
Šķirošanas ar Hoāra metodi funkcijas blokshēma
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;
}
}
void quicksort ( int N, int a[])
{
int p=a[N/2], temp;
int i=0, j=N-1; //pirmā un pēdējā elementu indeksi
do
{
while ( a[i] < p ) i++;
while ( a[j] > p ) j–;
if (i <= j)
{
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j–;
}
}
while ( i<=j );
//rekursija
if ( j > 0 ) quicksort(j, a);
if ( N > i ) quicksort(N-i, a+i);
}
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 if (number==4) shellsort(n,array);
else quicksort(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=4; f<6; f++)
//for (int f=1; f<6; 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 if (f==4) output<<endl<<“Shell Sort”<<endl;
else output<<endl<<“Quick Sort”<<endl;
for (int g=0; g<10; g++) for (int z=0; z<3; z++) rez[g][z]=0;
//laižam cauri šķirošanu 5 reizes pa 10 augošiem masīvu izmēriem
for (int a=0; a<5; a++)
{
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();
}
Iegūtie rezultāti un secinājumi
Hoāra šķirošanas metode, lai arī tika izstrādāta 40 gadus atpakaļ, šobrīd, spriežot pēc vairākiem literatūras avotiem, ir pati populārākā un visbiežāk pielietojamā tās ātrdarbības pēc. Arī manu eksperimentu rezultātā Hoāra metode bija visātrākā, apsteidzot arī Šella metodes iegūtos rezultātus.
Kā redzams no iegūto rezultātu grafiskā attēlojuma (1.attēls, 3.attēls), pilnīgi sakārtotam masīvam un masīvam, kas sakārtots pretējā secībā, šķirošana ar Hoāra metodi uzrādīja laiku, kas praktiski tuvs nullei. Tomēr, šķirojot šos masīvus, arī šķirošana ar ievietošanas un Šella metodēm uzrādīja līdzīgus laikus. Tātad ir jāizpēta vissīkāk šķirošana masīvam, kas ģenerēts ar nejaušiem skaitļiem, turklāt atsevišķi jāapskata šķirošana ar Šella un Hoāra metodēm lielākiem masīviem.
Jau no grafika (2.attēls) redzams, ka šķirojot nejauši ģenerētu masīvu, tiek atspoguļotas visas piecas metodes. Tomēr šķirošana ar Šella metodi un šķirošana ar Hoāra metodi uzrādīja tik labus rezultātus, ka to tuvākai izpētei es notestēju programmu vēlreiz tikai šīm divām šķirošanas metodēm, palielinot desmitkārt šķirojamo elementu skaitu (100’000-109’000 elementi).
Apskatot izveidotās līknes, kas iegūtas, apkopojot šķirošanas rezultātus, redzams, ka visu trīs masīvu veidu gadījumā šķirošana ar Hoāra metodi ir ātrāka. Pilnīgi sakārtotam masīvam (4.attēls) un masīvam, kas sakārtots pretējā secībā (6.attēls), grafiku līknes atrodas samērā tuvu. Tomēr masīvam, kas sastāv no nejauši ģenerētiem skaitļiem, šķirošana ar Hoāra metodi, salīdzinājumā ar šķirošanu ar Šella metodi, uzrādīja rezultātus, kas praktiski tuvu nulles laikam.
Līdz ar to varu izdarīt secinājumus, ka šķirošana ar Hoāra metodi ir visefektīgākā šķirošanas metode no visām apskatītajām, un tās efektivitāte palielinās, palielinoties masīva izmēriem.
Atbilstoši literatūras avotiem, katra sadalīšana pieprasa Teta(n) operācijas (n – elementu skaits masīvā). Dalījuma soļu skaits (rekursijas dziļums) ir apmēram log n, ja masīvs tiek dalīts apmēram vienādās daļās. Līdz ar to kopējā ātrdarbība ir O (n log n), kā tas bieži notiek, praktiski realizējot algoritmu.
Algoritms ir diezgan vienkāršs uztveršanā, bet ļoti sarežģīts realizācijā izmantojamās rekursijas dēļ. Šīs pašas rekursijas dēļ palielinās izmantojamās atmiņas apjoms, jo rekursijas aptuvenais dziļums ir O (log n), un dati par rekursijas izsaukšanu katru reizi tiek pievienoti atmiņas stekā.
Šķirošanas ar Hoāra metodi algoritms nav stabils, kas ir saprotams, ja ņem vērā, ka daļēji sakārtota masīva gadījumā palielinās iespējas sadalīt masīvu vienlīdz lielās daļās.
Sandra Lobazova
02.06.2006.