Triedenie poľa komplexných čísel (riešené príklady)
Majme známu štruktúru komplexné číslo - CPLX. Ako iste viete, komplexné číslo obsahuje 2 časti:reálnu časť (re) a imaginárnu časť (im). Ľubovoľné komplexné číslo C=a+i*b dokážeme zobraziť v komplexnej rovine ako vektor so začiatkom v bode [0,0] a koncom v bode C=[a,b].
Veľkosť komplexného čísla |C| je vlastne vzdialenosť od počiatku súradnicovej sústavy. Vypočítame ho pomocou pytagorovej vety ako: |C|=(a*a+b*b)^1/2
Majme pole komplexných čísel, ktoré chceme zotriediť podľa ich veľkosti. V hlavnom programe main načítam číslo n a následne n komplexných čísel. Tieto komplexné čísla načítajte do jednorozmerného poľa komplexných čísel, ktoré má presne veľkosť n (použite dynamickú alokáciu).
Ako triediaci algoritmus použijeme quicksort, pretože je značne efektívny. Metóda triedenia quicksort bola vysvetlená na prednáške. Len v krátkosti: quicksort je rekurzívny algoritmus, ktorý si rozdelí usporiadavané pole na 2 časti: prvky v prvej časti sú menšie ako stredný prvok (pivot) a prvky v druhej časti sú väčšie ako stredný prvok. Potom sa rekurzívne aplikuje algoritmus quickosrt na prvú aj druhú časť triedeného poľa, pokiaľ je počet prvkov v danej časti poľa väčší ako 1.
V tomto príklade usporiadavame pole celých čísel. Našou úlohou je ale usporiadať pole komplexných čísel. Vo funkcii QuickSort sa zmení prvý parameter na pole komplexných čísel: CPLX data[]. Ďalej je treba zmeniť tú časť kódu, kde sa navzájom porovnávajú prvky triedeného poľa (podčiarknuté časti kódu). V tomto prípade sú to dva cykly while, kde sa určujú indexy i a j, ktoré slúžia pri usporiadavaní poľa na časť väčšiu a menšiu ako je pivot. Tieto časti kódu nahradíme porovnávacou funkciou, ktorá bude porovnávať dve komplexné čísla x a y. Ak platí že x>y, tak funkcia vráti 1, inak vráti 0. Týmto zručíme rovnakú funkcionalitu ako relačný operátor ‘>’. Funkcia bude mať 2 parametre typu CPLX a návratová hodnota bude int.
1 int porovnaj(CPLX a, CPLX b)
2 {
3 if(abs(a)>abs(b))
4 return 1;
5 else
6 return 0;
7 }
Na skontrolovanie správnosti usporiadania poľa komplecných čísel môžeme použiť jednoduchú funkciu, ktorá overí či prvok s indexom i+1 je väčší ako prvok s indexom i. Pri prvej nezhode funkcia vráti hodnotu 0. Ak sa pre všetky prvky platí predpoklad prvok[i+1]>prvok[i] , tak vráti funkcia hodnotu 1.
1 int skontroluj(CPLX data[ ],int n)
2 {
3 for(int i=1;i
4 {
5 if(porovnaj(data[i-1],data[i])>1)
6 return 0;
7 }
8 return 1;
9 }
Ak máme pripravenú porovnávaciu funkciu, tak aplikovanie iného algoritmu triedenia je veľmi jednoduché. Stačí v danom kóde zameniť časť kódu, kde sa robí porovnávanie prvkov. Jazyk C obsahuje vstavanú funkciu qsort, ktorá usporiadava pole prvkov pomocou algoritmu quicksort. Hlavička funkcie vyzerá nasledovne:
void qsort(void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *));
Opis funkcie qsort je na stránke qsort
Použitie funkcie qsort pre náš príklad:
qsort((void *)ccisla2,n,sizeof(ccisla2[0]),porovnajQ);
1 int porovnajQ(const void *a, const void *b)
2 { if(abs((*(CPLX *)a))>abs((*(CPLX *)b)))
3 return 1;
4 if(abs((*(CPLX *)a))<abs((*(CPLX *)b)))
5 return -1;
6 return 0;
7 }
Podľa definície funkcie qsort musí mať porovnávacia funkcia 2 argumenty typu ukazateľ na void. Teda parametre a a b sú typu ukazateľ na void. My však potrebujeme porovnať 2 komplexné čísla (bez ukazovateľov). Ako prvé musíme a a b pretypovať z ukazateľa na void na ukazateľ na CPLX. Toto urobíme následovne: (CPLX *)a.Teraz je a ukazateľ na CPLX. Ale ako už bolo povedané, my máme k dispozícii len komplexné čísla (CPLX), nie ukazatele. Z teórie ukazateľov vieme vzťah medzi ukazateľom a poľom – že ak je x ukazovateľ na nejaký dátový typ, tak *x je obsah prvého (s indexom 0) prvku. Teda, ak je (CPLX *)a ukazovateľ na CPLX, tak(*(CPLX *)a)je obsah tohto ukazateľa – čiže komplexné číslo a.
Na záver porovnajte, či oba algoritmy dosahujú zhodné výsledky – stačí porovnať polia usporiadané funkciou QuickSort a funkciou qsort.
1 int skontroluj(CPLX data1[ ],CPLX data2[ ],int n)
2 { for(int i=0;i<n;i++)
3 if(porovnaj(data1[i],data2[i])!=0)
4 return 0;
5 return 1;
6 }
Možné riešenie:
1 #include <iostream>
2 #include <math.h>
3 using namespace std;
4
5 struct CPLX{double re,im;};
6
7 void nacitajCPLX(CPLX &c)
8 { cin>>c.re>>c.im; }
9
10 double abs(CPLX x)
11 { return sqrt( (x.re*x.re)+ (x.im*x.im) ); }
12
13 int porovnaj(CPLX a, CPLX b)
14 { if(abs(a)>abs(b))
15 return 1;
16 else
17 return 0;
18 }
19
20 void zamen (CPLX &a, CPLX &b)
21 {
22 CPLX tmp=a;
23 a=b;
24 b=tmp;
25 }
26
27 void QuickSort(CPLX data[ ],int lavy, int pravy)
28 { if(lavy<pravy)
29 { int i = lavy, j = pravy;
30 CPLX p = data[ (lavy + pravy) / 2 ];
31 do {
32 while ( porovnaj(p,data[ i ])>0 ) i++;
33 while ( porovnaj(data[ j ],p)>0 ) j--;
34 if (i <= j)
35 { zamen(data[ i ], data[ j ]);
36 i++; j--;
37 }
38 } while (i <= j);
39 QuickSort(data, lavy, j);
40 QuickSort(data, i, pravy);
41 }
42 }
43
44 int skontroluj(CPLX data[ ],int n)
45 { for(int i=1;i<n;i++)
46 if(porovnaj(data[i-1],data[i])>0)
47 return 0;
48 return 1;
49 }
50
51 int skontroluj(CPLX data1[ ],CPLX data2[ ],int n)
52 { for(int i=0;i<n;i++)
53 if(porovnaj(data1[i],data2[i])!=0)
54 return 0;
55 return 1;
56 }
57
58 void vypis(CPLX data[ ],int n)
59 { for(int i=0;i<n;i++)
60 { cout<<data[i].re;
61 if(data[i].im>0)
62 cout<<"+i"<<data[i].im;
63 else
64 cout<<"-i"<<-data[i].im;
65 cout<<" ("<<abs(data[i])<<")";
66 cout<<endl;
67 }
68 }
69
70 int porovnajQ(const void *a, const void *b)
71 { if(abs((*(CPLX *)a))>abs((*(CPLX *)b)))
72 return 1;
73 if(abs((*(CPLX *)a))<abs((*(CPLX *)b)))
74 return -1;
75 return 0;
76 }
77
78 int main()
79 { int n;
80 cin>>n;
81 CPLX *ccisla1=new CPLX[n];
82 CPLX *ccisla2=new CPLX[n];
83
84 for(int i=0;i<n;i++)
85 { nacitajCPLX(ccisla1[i]);
86 ccisla2[i]=ccisla1[i];
87 }
88
89 int k;
90 QuickSort(ccisla1,0,n-1);
91 k=skontroluj(ccisla1,n);
92 cout<<"kontola QuickSort:"<<k<<endl;
93
94 qsort((void *)ccisla2,n,sizeof(ccisla2[0]),porovnajQ);
95 k=skontroluj(ccisla2,n);
96 cout<<"kontola qsort:"<<k<<endl;
97 k=skontroluj(ccisla1,ccisla2,n);
98 cout<<"Kontrola zhodnosti: "<<k;
99 return 0;
100 }
