Třídění

(2015)

Na základě látky odpřednášené na přednáškách naprogramujte co nejvíce algoritmů na třídění (zatím statických) polí.

Třídění dat – bubble sort

1) Otevřete soubor jehož jméno je na příkazové řádce dodáno programu jako parametr. Program dopracujte tak, aby ošetřil možné chybové stavy a aby se choval korektně (kontrola chyb, uzavření souboru. Inspirovat se můžete zde.

2) Z otevřeného souboru ve funkci načtěte data. Funkce bude mít jako parametr otevřený soubor, vrátí počet načtených hodnot a v případě chyby načítání vrátí záporné číslo int Nacti(FILE* aFile, int aPole[], int aVelikostPole). Pole bude definované ve volající funkci (main) a bude (prozatím) statické o (maximální) délce 1000 hodnot (nadefinujte jako makro MAXSIZE). Data v souboru budou celočíselná, jedna hodnota na řádek, bez oddělovačů (jediným bude takzvaný „bílý“ znak nového řádku). Počet hodnot není předem znám, je nutné ho zjistit během načítání.

3) Napište funkci na tisk hodnot v celočíselném poli. Funkce void Tisk(int aPole[],int aPocet). Tisk proveďte ve formátu „index: Hodnota“ - index je pozice v poli.

4) Napište funkci Setrid, která k setřídění pole od nejmenšího k největšímu prvku použije algoritmu bubble sort. Setřídění provede v původním poli. Hlavička bude void Setrid(int aPole[], int aDelka). Po setřídění data (ve funkci main) vytiskněte zavoláním funkce Tisk() a zkontrolujte správnost třídění.

5) V některých aplikacích není možné manipulovat/třídit původní pole. Pokud jsou data v poli značně rozsáhlá, není vhodné (a někdy ani možné) vytvořit kopii pole. Proto se používá třídění pomocí pomocného pole indexů. Napište funkce z bodů 3 a 4 tak, aby pracovaly s polem indexů. Pole indexů nadefinujte a inicializujte ve funkci main.

- Napište funkci na tisk hodnot v celočíselném poli. Funkce void TiskIndex(int aPole[],int aIndex[],int aPocet). Tisk proveďte v „setříděném“ tvaru ve formátu „poradi: index: Hodnota“ - index je pozice v poli hodnot (tj. určí který prvek z pole hodnot se bude tisknout), poradi je pořadi indexu (tj bude nabývat hodnot 0,1,2,3...), hodnota je hodnota z pole hodnot.

- Napište funkci SetridIndex, která k setřídění pole od nejmenšího k největšímu prvku použije algoritmu bubble sort, ale nebude třídit vlastní data ale třídění provede pomocí indexů do původních dat. Setřídění indexů provede v původním poli. Hlavička bude void SetridIndex(int aPole[], int aIndex[], int aDelka). Po setřídění data (ve funkci main) vytiskněte zavoláním funkce TiskIndex() a zkontrolujte správnost třídění.

Bubble sort (bublinkové třídění)

-probublávání prvků,

-lze vytvořit různé varianty pro oba směry (zleva, zprava) a oba způsoby (od nejmenšího, od největšího)

Algoritmus pro třídění od nejmenšího:

1) Postupně srovnávej sousední prvky zleva. Pokud je prvek vpravo menší, pak prvky vyměň (otoč pořadí). Tímto „probublá“ největší prvek na konec (a v další iteraci už není nutné s ním pracovat).

2) Proveď bod 1) s polem o jedno kratším, pokud je (zbylá část) pole delší než jeden prvek

Algoritmus lze zrychlit například tím, že si pamatujeme místo, kde nastala poslední výměna – pole potom nezkracujeme o jeden prvek ale po místo poslední výměny

Data pro test třídění mohou vypadat například takto

-10
20
0
200
50
40
45
-50
-40
-45
0
-100
200

Poslední změna 2015-03-19