Triedenie poľa smerníkov na komplexné čísla (riešené príklady)
Obsah
Zadanie
Vytvorte program, ktorý usporiada pole komplexných čísel. Úlohu riešte pomocou vstavanej funkcie jazyka C qsort a algoritmu Quick sort. Úlohu riešte pomocou jednorozmerného poľa smerníkov na komplexné číslo. Porovnajte dosiahnuté rýchlosť výpočtu tohoto riešenia a predchádzajúceho príkladu riešeného pomocou poľa komplexných čísel.
Analýza riešenia
V analýze problému úlohy sa sústredíme len na to, čo je v riešení tejto úlohy nové oproti riešeniu predchádzajúcej úlohy Triedenie poľa komplexných čísel. V našej úlohe pracujeme s dynamickými poliami ukazovateľov na dátový typ CPLX, čiže v konečnom dôsledku s ukazovateľmi na štruktúrové premenné typu CPLX. Z toho dôvodu potrebujeme upraviť väčšinu funkcií z riešenia predchádzajúcej úlohy Triedenie poľa komplexných čísel (riešené príklady).
Vstupné a výstupné údaje
V programe načítajte číslo n a následne n komplexných čísel. Pre uloženie týchto čísel vytvorte také veľké pole smerníkov na komplexné číslo, aké je potrebné.
Triedenie pomocou funkcie QuickSort
V našej triediacej funkcii QuickSort z minulého príkladu musíme použiť upravenú funkciu porovnaj . Jej úprava spočíva v zmene typu jej argumentov na typ ukazovateľ na štruktúrovú premennú typu CPLX, pretože vo funkcii main chceme vytvoriť a používať pole ukazovateľov na dátový typ CPLX.
Definícia funkcie porovnaj
Definícia funkcie porovnaj je teraz nasledovná
int porovnaj(CPLX *a, CPLX *b)
{
if(abs(a)>abs(b))
return 1;
else
return 0;
}
Parametre funkcie
a, b – ukazovatele na dátový typ CPLX, čiže na komplexné čísla, ktoré budeme porovnávať.
Návratová hodnota
- 1 - ak platí, že
hodnota komplex. čísla, na ktoré ukazuje ukazovateľ a > hodnota komplex. čísla, na ktoré ukazuje ukazovateľ b
- 0 – v ostatných prípadoch
Funkcia abs
Vo funkcii porovnaj voláme funkciu abs, ktorá očakáva argument dátového typu CPLX *, preto musíme nasledovne upraviť aj definíciu tejto funkcie
double abs(CPLX *x)
{
return sqrt( (x->re * x->re) + (x->im * x->im) );
}
Parametre funkcie
x – ukazovateľ na dátový typ CPLX, čiže na komplexné číslo, ktorého modul (veľkosť) funkcia vypočíta.
Návratová hodnota
modul, čiže veľkosť komplexného čísla, na ktoré ukazuje ukazovateľ x
Funkcia QuickSort
Použitie porovnávacej funkcie porovnaj v upravenej funkcii QuickSort vidíme v jej definícii
1 void QuickSort(CPLX **data, int lavy, int pravy)
2 {
3 if(lavy<pravy)
4 {
5 int i = lavy, j = pravy;
6 CPLX *p = data[ (lavy + pravy) / 2 ];
7 do
8 {
9 while ( porovnaj(p, data[i]) > 0 ) i++;
10 while ( porovnaj(data[j], p) > 0 ) j--;
11 if (i <= j)
12 {
13 CPLX *tmp = data[i];
14 data[i] = data[j];
15 data[j] = tmp;
16 i++;
17 j--;
18 }
19 }while (i <= j);
20 QuickSort(data, lavy, j);
21 QuickSort(data, i, pravy);
22 }
23 }
Parametre funkcie
- data – ukazovateľ na ukazovateľ na dátový typ CPLX, čiže v našom prípade ukazovateľ na pole ukazovateľov na dátový typ CPLX, pričom prvky poľa (komplexné čísla), na ktoré ukazujú tieto ukazovatele funkcia QuickSort usporiadava
- lavy – indexová premenná krajného ľavého prvku triedeného poľa
- pravy – indexová premenná krajného pravého prvku triedeného poľa
Návratová hodnota
je typu void – funkcia nevráti žiadnu návratovú hodnotu
Funkcia porovnaj
Taktiež sme museli upraviť funkciu skontroluj, ktorá kontroluje správne usporiadanie prvkov poľa, na ktoré ukazujú ukazovatele typu CPLX *, čiže usporiadanie štruktúrových premenných typu CPLX, vzostupne podľa ich veľkosti. Upravená definícia tejto funkcie je nasledovná
1 int skontroluj(CPLX *data[],int n)
2 {
3 for(int i=1;i<n;i++)
4 if(porovnaj(data[i-1],data[i])>0)
5 return 0;
6 return 1;
7 }
Funkcia overuje či prvok poľa komplexných čísiel, na ktorý ukazuje ukazovateľ data[i] je väčší, ako prvok tohto poľa, na ktorý ukazuje ukazovateľ data[i-1]. Pri prvej dvojici prvkov neusporiadanej podľa tohto pravidla funkcia vráti 0, ak sú všetky prvky tohto poľa usporiadané vzostupne, funkcia vráti 1.
Parametre funkcie
- data – ukazovateľ na pole ukazovateľov na dátový typ CPLX. Ukazovatele v tomto poli ukazujú na dátový typ CPLX, teda na štruktúrové premenné tohto typu, v ktorých sú uložené komplexné čísla
- n – počet prvkov poľa ukazovateľov na dátový typ CPLX
Návratová hodnota
- 1 - prvky poľa komplexných čísiel, na ktoré ukazujú ukazovatele v poli ukazovateľov data sú usporiadané vzostupne
- 0 - prvky poľa komplexných čísiel, na ktoré ukazujú ukazovatele v poli ukazovateľov data nie sú usporiadané vzostupne
Triedenie pomocou knižničnej funkcie qsort
Jazyk C obsahuje vstavanú funkciu qsort, ktorá usporiadava pole prvkov pomocou algoritmu Quick sort.
Volanie funkcie qsort vo funkcii main nášho príkladu vyzerá nasledovne:
qsort((void *)ccisla2ptp, n, sizeof(ccisla2ptp[0]), porovnajQptp);
V tomto volaní je dôležitá porovnávacia funkcia porovnajQptp, ktorej hlavička a iné vlastnosti sú určené, avšak jej telo sme si museli vytvoriť sami
int porovnajQptp(const void *a, const void *b)
{
if(abs(*(CPLX **)a) > abs(*(CPLX **)b))
return 1;
if(abs(*(CPLX **)a) < abs(*(CPLX **)b))
return -1;
return 0;
}
V hlavičke funkcie predpísané typy parametrov sme si museli v tele funkcie qsort vo volaniach funkcie abs pretypovať na typy korektné pre túto funkciu. Najskôr pretypujeme ukazovatele const void * na ukazovateľ CPLX ** a potom tieto ukazovatele dereferencujeme na ukazovatele CPLX *, pretože takýto typ argumentu požaduje funkcia abs. Okrem iného je to aj typ prvku poľa ukazovateľov na CPLX. Postupnosť týchto pretypovaní je nasledovná:
const void *a //’a‘ je ukazovateľ typu ‘const void *‘
(CPLX **)a //pretypujeme ho na ukazovateľ typu ‘CPLX **‘
*(CPLX **)a //a teraz ho dereferencujeme na ukazovateľ typu ‘CPLX *‘, pretože ukazovateľ takého
//typu potrebuje v argumente funkcia ‘abs‘
Komplexné čísla nášmu programu nebude zadávať používateľ, ale ich vygeneruje zavolaná funkcia generujCPLX, ktorej definícia je nasledovná
void generujCPLX(CPLX *c)
{
c->re = 1+ ( rand()%MAX_CISLO_1 );
c->im = 1+ ( rand()%MAX_CISLO_2 );
}
Parametre funkcie
c – ukazovateľ na dátový typ CPLX, čiže na štruktúrovú premennú typu CPLX (komplexné číslo), ktorej vnútorné premenné napĺňa funkcia vygenerovanými hodnotami.
Návratová hodnota
je typu void – funkcia nevráti žiadnu návratovú hodnotu
Príklad vstupu a výstupu programu
Vzorový vstup
velkost triedeneho pola: 100000
Vzorový výstup
QuickSort: trvanie: 0.01 s qsort: trvanie: 8 s
Zdrojový kód riešenia
Úlohou programu je porovnať rýchlosť oboch implementovaných algoritmov triedenia. Aby mali oba algoritmy rovnaké počiatočné podmienky, vytvoríme si dve zhodné polia komplexných čísel (ccisla1ptp, ccisla2ptp). Potom bude každý algoritmus triediť rovnaké vstupné dáta.
1 #include <iostream>
2 #include <math.h>
3 #include <time.h>
4
5 using namespace std;
6 struct CPLX{ double re, im; };
7
8 //Funkcia ocakava v 1 argumente ukazovatel na na strukturovu premennu typu 'CPLX'.
9 //Funkcia vygeneruje komplexne cislo pomocou generatora pseudonahodnych cisiel 'rand'.
10 //nahodne cisla su generovane v rozsahu 0..RAND_MAX co je 32767
11 void generujCPLX(CPLX *c)
12 {
13 c->re = 1+ (rand());
14 c->im = 1+ (rand());
15 }
16
17 //Funkcia ocakava v 1. argumente ukazovatel na strukturovu premennu typu 'CPLX'.
18 //Funkcia vypocita modul komplexneho cisla (cize jeho velkost).
19 double abs(CPLX *x)
20 {
21 return sqrt( (x->re * x->re) + (x->im * x->im) );
22 }
23
24 //Funkcia ocakava 2 ukazovatele na strukturove premenne typu 'CPLX' ako argumenty.
25 //Funkcia podla velkosti vzajomne porovna strukturove premenne typu 'CPLX', na ktore ukazuju
26 //ukazovatele 'a' a 'b'.
27 int porovnaj(CPLX *a, CPLX *b)
28 {
29 if(abs(a)>abs(b))
30 return 1;
31 else
32 return 0;
33 }
34
35 //Funkcia triedi pole strukturovych premennych algoritmom Quick sort.
36 //Je jedno ci je jej prvym argumentom 'CPLX **data' alebo 'CPLX *data[]', pretoze oba syntakticky
37 //v nasom pripade predstavuju ukazovatel na pole ukazovatelov na strukturove premenne typu 'CPLX'.
38 //Funkcia s oboma argumentami funguje spravne.
39 void QuickSort(CPLX **data, int lavy, int pravy)
40 {
41 if(lavy<pravy)
42 {
43 int i = lavy, j = pravy;
44 CPLX *p = data[ (lavy + pravy) / 2 ];
45 do
46 {
47 while ( porovnaj(p, data[i])>0 ) i++;
48 while ( porovnaj(data[j], p)>0 ) j--;
49 if (i <= j)
50 {
51 CPLX *tmp = data[i];
52 data[i] = data[j];
53 data[j] = tmp;
54 i++; j--;
55 }
56 }while (i <= j);
57 QuickSort(data, lavy, j);
58 QuickSort(data, i, pravy);
59 }
60 }
61
62 //Funkcia ocakava v 1 argumente ukazovatel na pole ukazovatelov na strukturove premenne
63 //typu 'CPLX'. V tele potom pracuje s prvkami 'data[i]'(cize s ukazovatelmi) tohto pola ukazovatelov
64 //na strukturove premenne typu 'CPLX'.
65 //Funkcia skontroluje spravne usporiadanie prvkov pola,
66 //cize usporiadanie strukturovych premennych typu 'CPLX' vzostupne podla ich velkosti.
67
68 //Je jedno ci je jej prvym argumentom 'CPLX **data' alebo 'CPLX *data[]', pretoze oba syntakticky
69 //v nasom pripade predstavuju ukazovatel na pole ukazovatelov na strukturove premenne typu 'CPLX'.
70 //Funkcia s oboma argumentami funguje spravne.
71 int skontroluj(CPLX *data[],int n)
72 {
73 for(int i=1;i<n;i++)
74 if(porovnaj(data[i-1],data[i])>0)
75 return 0;
76 return 1;
77 }
78
79 //porovnavacia funkcia do kniznicnej funkcie 'qsort'
80 int porovnajQptp(const void *a, const void *b)
81 {
82 if(abs(*(CPLX **)a) > abs(*(CPLX **)b))
83 return 1;
84 if(abs(*(CPLX **)a) < abs(*(CPLX **)b))
85 return -1;
86 return 0;
87 }
88
89 int main()
90 {
91 int n, i;
92 cout<<"velkost triedeneho pola: ";
93 cin>>n;
94
95 //'ccisla1ptp' je ukazovatel na ukazovatel na CPLX
96 CPLX **ccisla1ptp=new CPLX*[n]; //alokovanie miesta pre n-prvkove POLE UKAZOVATELOV na
97 //CPLX, na ktore ukazuje ukazovatel 'ccisla1ptp'
98 for(i=0; i<n; i++)
99 ccisla1ptp[i]=new CPLX; //inicializacia ukazovatela 'ccisla1ptp[i]', vkladame do neho ukazovatel na
100 //pamatove miesto pre premennu typu CPLX
101
102 CPLX **ccisla2ptp=new CPLX*[n];
103 for(i=0; i<n; i++)
104 ccisla2ptp[i]=new CPLX;
105
106 //nastavenie startovacieho cisla generatora pseudonahodnych cisiel 'rand', aby toto cislo bolo
107 //vzdy ine, po novom zavolani funkcie 'main'. Takto tento generator vygeneruje vzdy ine pseudonahodne cisla
108 srand( (unsigned)time( NULL ) );
109
110 //plnenie obsahu prvkov pola 'ccisla1ptp' a 'ccisla2ptp' vygenerovanymi komplexnymi cislami
111 for(i=0; i<n; i++)
112 {
113 generujCPLX(ccisla1ptp[i]);
114 ccisla2ptp[i]=ccisla1ptp[i];
115 }
116
117 int k;
118 clock_t c1, c2;
119
120 c1 = clock();
121 QuickSort(ccisla1ptp, 0, n-1);
122 c2 = clock();
123 k=skontroluj(ccisla1ptp, n);
124 if(k)
125 cout<<"QuickSort: trvanie "<< (c2 - c1)/CLOCKS_PER_SEC << " s"<<endl;
126 else
127 cout<<"Pole nie je utriedene!";
128
129 c1 = clock();
130 qsort((void *)ccisla2ptp, n, sizeof(ccisla2ptp[0]), porovnajQptp);
131 c2 = clock();
132 k=skontroluj(ccisla2ptp, n);
133 if(k)
134 cout<<"qsort: trvanie "<< (c2 - c1)/CLOCKS_PER_SEC << " s"<<endl;
135 else
136 cout<<"Pole nie je utriedene!";
137
138 for(i=0;i<n;i++)
139 {
140 delete ccisla1ptp[i]; //mazeme pole ukazovatelov
141 delete ccisla2ptp[i];
142 }
143 delete[] ccisla1ptp; //mazeme ukazovatel na toto pole
144 delete[] ccisla2ptp;
145
146 return 0;
147 }
Záver
Z výsledkov merania času doby behu programu sme zistili že knižničná funkcia qsort je niekoľkokrát pomalšia ako nami implementovaný algoritmus QuickSort. Táto skutočnosť je zapríčinená univerzálnou štruktúrou funkcie qsort, v ktorej môžeme triediť pole ľubovoľného dátového typu. Pri jej použití sa musia prvky triedeného typu niekoľkokrát pretypovať z ukazateľa na konkrétny dátový typ (u nás CPLX) na ukazovateľ na void. Toto zaberá väčšinu času. Naša implementácia algoritmu QuickSort je priamo naprogramované pre usporiadania dátovej štruktúry CPLX a netreba žiadne ďalšie pretypovania, čím sa ušetrí výpočtový čas
