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 }
