Triedenie(riešené príklady) - História úprav

Juraj na 20:28, 16. august 2010

2010-08-16T20:28:40Z

Juraj na 18:15, 8. marec 2010

2010-03-08T18:15:49Z

Juraj na 14:14, 8. marec 2010

2010-03-08T14:14:41Z

Juraj na 14:12, 8. marec 2010

2010-03-08T14:12:41Z

Zobraziť rozdiely

Juraj: /* Návod ako začať */

2010-03-08T13:52:05Z

Návod ako začať

Juraj na 08:23, 3. marec 2010

2010-03-03T08:23:12Z

Juraj na 21:40, 23. február 2010

2010-02-23T21:40:04Z

Zobraziť rozdiely

Mstepanovsky na 21:04, 23. február 2010

2010-02-23T21:04:39Z

Zobraziť rozdiely

Mstepanovsky na 16:01, 23. február 2010

2010-02-23T16:01:43Z

Juraj: /* Triedenie poľa ukazovateľov aneb Triedime štruktúry efektívne */

2010-02-23T12:40:11Z

Triedenie poľa ukazovateľov aneb Triedime štruktúry efektívne

← Staršia verzia		Verzia zo dňa a času 20:28, 16. august 2010
Riadok 1:		Riadok 1:
−	~~[[Kategória:Študijné materiály]]~~
−	~~[[Kategória:Programovanie]]~~
−	~~[[Kategória:jazyk C]]~~
	{{Draft}}		{{Draft}}
	{{Skripta programovanie (zbierka úloh)}}		{{Skripta programovanie (zbierka úloh)}}

@@ Riadok 7: / Riadok 7: @@
 ==Triedenie poľa komplexných čísel==
 ===Zadanie===
-Úlohou je ale usporiadať pole komplexných čísel.
+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).
 Viac na [[Triedenie poľa komplexných čísel (riešené príklady)]]

@@ Riadok 4: / Riadok 4: @@
 {{Draft}}
 {{Skripta programovanie (zbierka úloh)}}
 ==Triedenie poľa štruktúr==

@@ Riadok 46: / Riadok 46: @@
   --------------------------------------------------------
 ===Návod ako začať===
-Zo zadania vyplýva, že hlavným účelom programu je triediť (vzostupne príp. zostupne zoradzovať) zamestnancov podľa triediaceho kritéria (meno, priezvisko, rok). Aby sme pri manipulácii (triedení) s jednotlivými zamestnancami pracovali ucelene so všetkými dátami vzťahujúcimi sa ku konkrétnemu zamestnancovi naraz, bude výhodné použiť štruktúru, ktorá nám tieto dáta takpovediac "zabalí". Takto budeme mať údaje o jednom zamestnancovi pohromade a budeme môcť s nimi pohodlne manipulovať. Týmto sme vyriešili problém ako reprezentovať jedného zamestnanca. Teraz sa vynára otázka ako efektívne pracovať s celým súborom zamestnancov. Pretože vieme, že v zdrojovom súbore sa nebude nachádzať viac ako 100 zamestnancov, bude vcelku výhodné použiť statické pole štruktúr na pamätanie všetkých zamestnancov. Dĺžka tohto poľa bude 100 položiek. Jedna položka poľa potom bude predstavovať jedného konkrétneho zamestnanca. Utriedenie zamestnancov potom budeme realizovať utriedením tohto poľa. Pre triedenie poľa ponúka knižnica ''stdlib.h'' funkciu rýchleho triedenia ''qsort''. Parametre a použitie funkcie ''qsort'' z knižnice ''stdlib.h'' si teraz vysvetlíme.
+Zo zadania vyplýva, že hlavným účelom programu je triediť (vzostupne príp. zostupne zoradzovať) zamestnancov podľa triediaceho kritéria (meno, priezvisko, rok). Aby sme pri manipulácii (triedení) s jednotlivými zamestnancami pracovali ucelene so všetkými dátami vzťahujúcimi sa ku konkrétnemu zamestnancovi naraz, bude výhodné použiť štruktúru, ktorá nám tieto dáta takpovediac "zabalí". Takto budeme mať údaje o jednom zamestnancovi pohromade a budeme môcť s nimi pohodlne manipulovať. Týmto sme vyriešili problém ako reprezentovať jedného zamestnanca. Teraz sa vynára otázka ako efektívne pracovať s celým súborom zamestnancov. Pretože vieme, že v zdrojovom súbore sa nebude nachádzať viac ako 100 zamestnancov, bude vcelku výhodné použiť statické pole štruktúr na pamätanie všetkých zamestnancov. Dĺžka tohto poľa bude 100 položiek. Jedna položka poľa potom bude predstavovať jedného konkrétneho zamestnanca. Utriedenie zamestnancov potom budeme realizovať utriedením tohto poľa. Pre triedenie poľa ponúka knižnica ''stdlib.h'' funkciu rýchleho triedenia ''qsort''. Parametre a použitie funkcie ''qsort'' z knižnice ''stdlib.h'' sú na stránke [[Qsort (jazyk C)|qsort]].
 ===Možné riešenie v jazyku C===
 <source lang="c" line >

@@ Riadok 291: / Riadok 291: @@
 Druhým významným rozdielom je požiadavka na viacúrovňové triedenie. Pri písaní porovnávacích funkcií zohľadňujúcich tri úrovne priorít triediacih kritérií je výhodné začať od písania funkcií pre jednoúrovňové triedenie (pozri predchádzajúci príklad), tieto ďalej využiť pri písaní dvojúrovňových, a tieto spolu zasa pri písaní trojúrovňových. Takto môžeme veľmi jednoducho a prehľadne podľa potreby napísať rôzne mnohoúrovňové porovnávacie funkcie.
 ===Možné riešenie v jazyku C===
 <source lang="c" line >
@@ Riadok 362: / Riadok 391: @@
     if((pole=(ZAMESTNANEC**)malloc(maxPocet_zamestnancov*sizeof(ZAMESTNANEC*)))==NULL)
+    {
-       printf(" Nedostatok pamate!\n");
+       printf("Nedostatok pamete!\n");
        system("pause");
        exit(1);
+    }
     // Najprv si musime alokovat priestor pre prveho zamestnanca
@@ Riadok 375: / Riadok 414: @@
+    }
     // Nacitanie vsetkych zamestnancov zo suboru
     for(i=0; nacitajZAMESTNANEC(fr,pole[i]); i++)

@@ Riadok 77: / Riadok 77: @@
 int (*fcmp)(const void *elem1, const void *elem2);
 </source>
 Od funkcie ''fcmp'' sa vyžaduje aby vracala celé číslo v závislosti od výsledku porovnania argumentov ''elem1'' a ''elem2'' nasledovne:
 * ak *''elem1''  <  *''elem2''        potom ''fcmp'' vráti celé číslo < 0
@@ Riadok 87: / Riadok 88: @@
-''Poznámka'': Pri porovnávaní porovnávame obsahy argumentov ''elem1'' a ''elem2'', to znamená, že píšeme napr. *''elem1''  <  *''elem2'' namiesto ''elem1''  < ''elem2''. zápis ''elem1''  <  ''elem2'' by totiž znamenal, že máme porovnať hodnotu ''elem1'' a ''elem2'' čo by znamenalo, že máme porovnať nejaké adresy uložené v premenných ''elem1'' a ''elem2'' (tieto premenné sú ukazovatele a teda pamätajú adresu, nie samotnú štruktúru). Porovnanie ''elem1''  <  ''elem2'' by teda bolo syntakticky správne, ale nemalo by zmysel. Chceme predsa porovnávať zamestnancov a nie adresy pamäte kde sú títo zamestnanci uložení.
+''Poznámka'': Pri porovnávaní porovnávame obsahy argumentov ''elem1'' a ''elem2'', to znamená, že píšeme napr. *''elem1''  <  *''elem2'' namiesto ''elem1''  < ''elem2''. Zápis ''elem1''  <  ''elem2'' by totiž znamenal, že máme porovnať hodnotu ''elem1'' a ''elem2'' čo by znamenalo, že máme porovnať nejaké adresy uložené v premenných ''elem1'' a ''elem2'' (tieto premenné sú ukazovatele a teda pamätajú adresu, nie samotnú štruktúru). Porovnanie ''elem1''  <  ''elem2'' by teda bolo syntakticky správne, ale nemalo by zmysel. Chceme predsa porovnávať zamestnancov a nie adresy pamäte kde sú títo zamestnanci uložení.
-Použitie funkcie ''qsort'' ilustrujme na nasledujúcom jednoduchom príklade:
+Použitie funkcie ''qsort'' ilustrujeme na nasledujúcom jednoduchom príklade:
 <source lang="c">
 #include <stdio.h>
@@ Riadok 110: / Riadok 111: @@
+{
    int n;
    qsort (pole, POCET_PRVKOV, sizeof(int), Porovnaj_cele_cisla);
    for (n=0; n<POCET_PRVKOV; n++)
       printf ("%d ",values[n]);
@@ Riadok 138: / Riadok 142: @@
 '''Zadanie'''
-Uvažujme rovnaké zadanie ako v predošlom s tým rozdielom, že načítané dáta nebudeme ukladať do poľa štruktúr. Navyše požadujme vnorené triedenie podľa triediaceho kritéria s nižšou prioritou ak sú položky podľa aktuálneho triediaceho kritéria ekvivalentné. V našom jednoduchom príklade to znamená, že ak napríklad triedime zamestnancov podľa krstného mena a mená niektorých zamestnancov sú rovnaké, potom budú títo utriedení podľa priezviska. Naopak, ak budeme triediť podľa priezviska a priezviská niektorých zamestnancov budú rovnaké, potom ich utriedime podľa krstného mena. Túto situáciu môžeme rozšíriť aj o triedenie podľa roku narodenia. V tomto prípade môžeme definovať prioritu jednotlivým triediacim kritériam a triediť následne podľa priorít.
+Uvažujme rovnaké zadanie ako v predošlom. Navyše požadujme viacúrovňové (vnorené) triedenie podľa triediaceho kritéria s nižšou prioritou ak sú položky podľa aktuálneho triediaceho kritéria ekvivalentné. V našom jednoduchom príklade to znamená, že ak napríklad triedime zamestnancov podľa krstného mena a mená niektorých zamestnancov sú rovnaké, potom budú títo utriedení podľa priezviska. Naopak, ak budeme triediť podľa priezviska a priezviská niektorých zamestnancov budú rovnaké, potom ich utriedime podľa krstného mena. Túto situáciu môžeme rozšíriť aj o triedenie podľa roku narodenia. V tomto prípade môžeme definovať prioritu jednotlivým triediacim kritériam a triediť následne podľa priorít.
@@ Riadok 152: / Riadok 156: @@
 '''Zjednodušujúce predpoklady'''
-:Rovnaké ako v predošlom s tým rozdielom, že počet záznamov v súbore nie je obmedzený. Predpokladáme však, že systém má dostatok voľnej pamäte. V súbore sa teda môže nachádzať niekoľko desiatok, ale aj stoviek tisícov záznamov.
+:Rovnaké ako v predošlom s tým rozdielom, že počet záznamov v súbore nie je obmedzený. Predpokladáme však, že systém má dostatok voľnej pamäte.
@@ Riadok 184: / Riadok 189: @@
 '''Návod ako začať'''
-Prvým významným rozdielom v porovnaní s predchádzajúcim zadaním je skutočnosť, že počet záznamov (zamestnancov) v súbore nie je obmedzený a je vopred neznámy. Z toho dôvodu je použitie statického poľa štruktúr neefektívne. Riešením je dynamická alokácia pamäte. Mohli by sme tak dynamicky alokovať pole štruktúr podľa aktuálnej potreby programu. Ak sa však zamyslíme nad požiadavkou efektívneho triedenia zamestnancov prichádzame k záveru, že ani toto riešenie by nebolo vhodné. Dôvodom je činnosť funkcie ''qsort'', ktorá pri triedení manipuluje s celými položkami poľa, ktoré by v tomto prípade boli štruktúry (keďže by sa jednalo o pole štruktúr či už staticky alebo dynamicky alokované). Funkcia ''qsort'' by tak musela pracovať pri triedení s pomerne veľkým objemom dát. Riešením tejto situácie je použitie dynamicky alokovaného poľa ukazovateľov. Jednotlivé položky poľa by potom už neboli samotné štruktúry, ale adresy týchto štruktúr. Ako vieme, veľkosť adresy je 4 bajty (resp. 8B v 64-bitovom OS). Takže funkcia ''qsort'' bude triediť pole adries tak aby po zotriedení boli splnené požiadavky triedenia dané prioritami triediacich kritérií.
+Prvým významným rozdielom v porovnaní s predchádzajúcim zadaním je skutočnosť, že počet záznamov (zamestnancov) v súbore nie je obmedzený a je vopred neznámy. Z toho dôvodu je použitie statického poľa štruktúr neefektívne. Riešením je dynamická alokácia pamäte. Mohli by sme tak dynamicky alokovať pole štruktúr podľa aktuálnej potreby programu. Ak sa však zamyslíme nad požiadavkou efektívneho triedenia zamestnancov prichádzame k záveru, že ani toto riešenie by nebolo vhodné. Dôvodom je činnosť funkcie ''qsort'', ktorá pri triedení manipuluje s celými položkami poľa, ktoré by v tomto prípade boli štruktúry (keďže by sa jednalo o pole štruktúr či už staticky alebo dynamicky alokované). Funkcia ''qsort'' by tak musela pracovať pri triedení s pomerne veľkým objemom dát. Riešením tejto situácie je použitie dynamicky alokovaného poľa ukazovateľov. Jednotlivé položky poľa by potom už neboli samotné štruktúry, ale adresy týchto štruktúr. Ako vieme, veľkosť adresy je 4 bajty (resp. 8B v 64-bitovom OS). Takže funkcia ''qsort'' bude triediť pole adries tak aby po zotriedení boli splnené požiadavky triedenia dané prioritami triediacich kritérií. Ak zhrnieme doteraz povedané, tak pre pamätanie celého súboru zamestnancov je výhodné použiť dynamicky alokované pole ukazovateľov, v ktorom pre každý prvok poľa budeme dynamicky alokovať pamäťový priestor pre pamätanie štruktúry uchovávajúcej údaje o jednom konkrétnom zamestnancovi.

@@ Riadok 143: / Riadok 143: @@
 '''Metodický komentár'''
-Cieľom tejto úlohy v porovaní s predchádzajúcou je efektívne triediť dáta použitím ukazovateľov a poukázať na ďalšie možnosti pri ich triedení.  Využijú sa pokročilejšie techniky práce s ukazovateľmi, dynamická alokácia a realokácia pamäte.
+:Cieľom tejto úlohy v porovaní s predchádzajúcou je efektívne triediť dáta použitím ukazovateľov a poukázať na ďalšie možnosti pri ich triedení.  Využijú sa pokročilejšie techniky práce s ukazovateľmi, dynamická alokácia a realokácia pamäte.
 '''Vzorové dáta'''
-  Ako v predošlom.
+:Ako v predošlom.
 '''Zjednodušujúce predpoklady'''
-  Rovnaké ako v predošlom s tým rozdielom, že počet záznamov v súbore nie je obmedzený. Predpokladáme však, že systém má dostatok voľnej pamäte. V súbore sa teda môže nachádzať niekoľko desiatok, ale aj stoviek tisícov záznamov.
+:Rovnaké ako v predošlom s tým rozdielom, že počet záznamov v súbore nie je obmedzený. Predpokladáme však, že systém má dostatok voľnej pamäte. V súbore sa teda môže nachádzať niekoľko desiatok, ale aj stoviek tisícov záznamov.