Triedenie poľa komplexných čísel (riešené príklady)

Algoritmy a programovanie - zbierka úloh

---

Štruktúry

Rekurzia

Dynamická alokácia pamäti

Vyhľadávanie

Triedenie

>Triedenie poľa komplexných čísel
>Triedenie poľa smerníkov na CPLX
>Triedenie poľa štruktúr
>Triedenie poľa smerníkov

Lineárny zoznam

Binárny strom

Numerické algoritmy

Zadanie

Vytvorte program, ktorý usporiada pole komplexných čísel. Úlohu riešte pomocou algoritmu Quicksort (definovaného v quicksort) a pomocou vstavanej funkcie jazyka C qsort. Porovnajte dosiahnuté výsledky (rýchlosť výpočtu).

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 aké je potrebné.

Analýza problému

Komplecné číslo pozostáva z 2 častí: reálna zložka a imaginárna zložka. Komplexné číslo C zapíšeme ako:

C=a+bi

Ľ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].

V jazyku C si pre komplexné číslo vytvoríme dátovú štruktúru, ktorá ho bude reprezentovať. V štruktúre definujeme 2 časti: reálnu (Re) a imaginárnu (Im). Obe časti sú typu double. Štruktúru si pomenujeme CPLX.

1 struct CPLX{
2    double Re,Im;
3 };

Veľkosť komplexného čísla |C| je vzdialenosť od počiatku súradnicovej sústavy. Vypočítame ho pomocou Pytagorovej vety ako:

[math]\left |C\right |=\sqrt{a^2+b^2}[/math]

Majme pole komplexných čísel, ktoré chceme zotriediť podľa ich veľkosti. V programe máme začítať hodnotu n a následne n komplexných čísel. Pre uloženie týchto čísel vytvoríme jednorozmerné pole komplexných čísel. Veľkosť poľa je daná hodnotou n. Pre vytvorenie takéhoto poľa použijeme dynamickú alokáciu pamäti.

Ako triediaci algoritmus použijeme Quicksort, pretože je efektívny.

V samotnom algorime triedenia sa vyskytujú časti, kde sa porovnávajú prvky poľa vzájomne medzi sebou. Jazyk C nedovoľuje porovnávanie premenných typu štruktúra. Aby sme dokázali porovnávať premenné typu CPLX (komplexné číslo) vytvoríme si porovnávaciu funkciu. Funkcia porovnaj bude mať 2 parametre - komplexné čísla ktoré budeme porovnávať. Návratová hodnota funkcie bude typu int.

Funkcia porovnaj:

int porovnaj(CPLX a, CPLX b)
{
  return abs(a)- abs(b) ;
}

Pre porovnanie hodnoty 2 komplexných čísel vypočítame absolútnu hodnotu každého komplexného čísla a porovnáme tieto hodnoty.

Parametre funkcie

a, b - komplexné čísla (dátový typ CPLX), ktoré budeme porovnávať.

Návratová hodnota

• kladné číslo - ak platí, že a>b
• záporné číslo - ak platí, že a<b
• 0 - ak platí, že a=b

Použitie porovnávacej funkcie

1   CPLX x, y;
2   // nacitanie hodnot x, y
3   if(porovnaj(x,y)>0)
4     cout<<"Cislo x je vascie ako y";
5   if(porovnaj(x,y)<0)
6     cout<<"Cislo x je mensie ako y";
7   else
8     cout<<"Cisla x a y su rovnake";
9 }

Na skontrolovanie správnosti usporiadania poľa komplexný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 -1. Ak sa pre všetky prvky platí predpoklad prvok[i+1]>prvok[i] , tak vráti funkcia hodnotu 0.

1 int skontroluj(CPLX *data,int n)
2 { 
3   for(int i=1;i<n;i++)
4   {
5     if(porovnaj(data[i-1],data[i])>1)
6         return -1;
7   }
8   return 0;
9 }

Ak máme pripravenú porovnávaciu funkciu, tak aplikovanie iného algoritmu triedenia je jednoduché. Stačí v danom kóde zameniť časť kódu, kde sa robí porovnávanie prvkov.

 1 void QuickSort(CPLX *data,int lavy, int pravy)
 2 {      if(lavy<pravy)
 3       {  int i = lavy, j = pravy;
 4           CPLX p = data[ (lavy + pravy) / 2 ];
 5           do {
 6                 while ( porovnaj(p,data[ i ])>0 ) i++;  // pouzitie funkcie porovnaj
 7                 while ( porovnaj(data[ j ],p)>0 ) j--;  // pouzitie funkcie porovnaj
 8                 if (i <= j)
 9                       {    zamen(data[ i ], data[ j ]);
10                          i++; j--;
11                     }
12                } while (i <= j);
13                 QuickSort(data, lavy, j);
14                 QuickSort(data, i, pravy);
15         }
16 }

Riešenie pomocou funkcie qsort

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);

kde porovnajQ je porovnávacia funkcia:

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:

a // ukazateľ na void
(CPLX *)a // a je ukazateľ na void pretypovaný na ukazateľ na CPLX
*(CPLX *)a // hondota komplexneho cisla, ktore sme ziskali
           // z ukazateľa na void a pretypovali na ukazateľ na CPLX

Riešenie v jazyku C

Úlohou 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 (ccisla1, ccisla2). Potom každýý algoritmus bude triediť rovnaké vstupné dáta.

 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 {  
15   return abs(a)-abs(b);
16 }
17 
18 void zamen (CPLX &a, CPLX &b)
19 {
20     CPLX tmp=a;
21     a=b;
22     b=tmp;
23 }
24 
25 void QuickSort(CPLX *data,int lavy, int pravy)
26 {      if(lavy<pravy)
27       {  int i = lavy, j = pravy;
28           CPLX p = data[ (lavy + pravy) / 2 ];
29           do {
30                 while ( porovnaj(p,data[ i ])>0 ) i++;
31                 while ( porovnaj(data[ j ],p)>0 ) j--;
32                 if (i <= j)
33                       {    zamen(data[ i ], data[ j ]);
34                          i++; j--;
35                     }
36                } while (i <= j);
37                 QuickSort(data, lavy, j);
38                 QuickSort(data, i, pravy);
39         }
40 }
41 
42 int skontroluj(CPLX data[ ],int n)
43 {   for(int i=1;i<n;i++)
44         if(porovnaj(data[i-1],data[i])>0)
45             return -1;
46     return 0;
47 }
48 
49 void vypis(CPLX *data,int n)
50 {  for(int i=0;i<n;i++)
51     {   cout<<data[i].re;
52         if(data[i].im>0)
53             cout<<"+i"<<data[i].im;
54         else
55             cout<<"-i"<<-data[i].im;
56         cout<<" ("<<abs(data[i])<<")";
57         cout<<endl;
58    }
59 }
60  
61 int porovnajQ(const void *a, const void *b)
62 {   if(abs((*(CPLX *)a))>abs((*(CPLX *)b)))
63         return 1;
64     if(abs((*(CPLX *)a))<abs((*(CPLX *)b)))
65       return -1; 
66      return 0;
67 }
68 
69 int main()
70 {   int n;     
71     cin>>n;
72     CPLX *ccisla1=new CPLX[n];
73     CPLX *ccisla2=new CPLX[n];
74 
75     for(int i=0;i<n;i++)
76     {  nacitajCPLX(ccisla1[i]);
77         ccisla2[i]=ccisla1[i];
78     }
79 
80     int k;
81     QuickSort(ccisla1,0,n-1);
82     k=skontroluj(ccisla1,n);
83     cout<<"kontola QuickSort:"<<k<<endl;
84 
85     qsort((void *)ccisla2,n,sizeof(ccisla2[0]),porovnajQ);
86     k=skontroluj(ccisla2,n);
87     cout<<"kontola qsort:"<<k<<endl;
88     return 0;
89 }

Pre meranie dĺžky trvania algoritmov môžeme použiť funkciu clock.