Úkolem je implementovat stabilní řadící algoritmus BucketSort, kde jednotlivé kyblíky budou seřazeny stabilními verzemi algoritmů ShakerSort a SelectSort. Funkce algoritmu mají následující rozhraní:

 counters  shakerSort ( item* pole, int size );
 counters  selectSort ( item* pole, int size );
 counters* bucketSort ( item* pole, int size );
Pro potřeby všech funkcí máte k dispozici tyto datové struktury:

struct item
{
  int x;
  int y;
};
x je hodnota, podle které bude řadící algoritmus provádět řazení.
y je hodnota, podle které se pozná, zda je řazení stabilní.
struct counters
{
  int size;
  int tests;
  int moves;
};
size je hodnota, která odpovídá počtu řazených dat.
tests je hodnota, která odpovídá počtu testů, která byla provedena s řazenými daty.
moves je hodnota, která odpovídá počtu přesunů řazených dat.
Tyto struktury již máte deklarované

Funkce shakerSort dostane parametrem vstupní pole řazených elementů a jeho délku. Funkce seřadí elementy uložené v poli dle pravidel ShakerSortu (viz níže). Seřazené elementy budou po proběhnutí algoritmu uloženy ve stejném poli. Funkce vrátí strukturu counters, která bude obsahovat počet řazených čísel, počet provedených testů a počet přesunů.

Pro implementaci použijte stabilní a datově citlivou verzi.
Počet testů odpovídá počtu provedených porovnání nad daty (viz pseudokód v přednášce řádek 5 a 12), ostatní porovnání ignorujte (test konce for-cyklu)
Počet přesunů odpovídá počtu přesunů elementů v poli, což v případě operace swap (prohození) jde o 3 přesuny.
Funkce selectSort dostane parametrem vstupní pole řazených elementů a jeho délku. Funkce seřadí elementy uložené v poli dle pravidel SelectSortu (viz níže). Seřazená elementy budou po proběhnutí algoritmu uloženy ve stejném poli. Funkce vrátí strukturu counters, která bude obsahovat počet řazených čísel, počet provedených testů a počet přesunů.

Pro implementaci použijte stabilní verzi.
Počet testů odpovídá počtu provedených porovnání nad daty (viz pseudokód v přednášce řádek 4), ostatní porovnání ignorujte (test konce for-cyklu)
Počet přesunů odpovídá počtu prohození elementů v poli. Za přesun považujte i prohození elementu se sebou.
Funkce bucketSort dostane parametrem vstupní pole řazených elementů a jeho délku. Funkce seřadí data uložené v poli dle pravidel BucketSortu (viz níže). Seřazená data budou po proběhnutí algoritmu uložena ve stejném poli. Funkce vrátí pole struktur counters, která budou obsahovat počtů řazených čísel, počet provedených testů a přesunů z jednotlivých volání ShakerSort a SelectSort. V poslední struktuře counters bude součet všech provedených testů a přesunů provedený v rámci celého algoritmu včetně testů a přesunů provedených ve volaných algoritmech. (POZOR!!! pole counterů bude vracet b+1 hodnot)

Počet kyblíků je number_buckets = zaokrouhleno_nahoru (size / 10) .
Rozřazení do kyblíku proveďte dle vzorce number_bucket = (value - minimal_value) * number_buckets / (maximal_value - minimal_value + 1), kde minimal_value je minimální hodnota v poli, maximal_value je maximální hodnota v poli a value je hodnota, podle které se řadí.
Pro liché kyblíky použijte ShakerSort, pro sudé SelectSort
Odevzdávejte zdrojový soubor, který obsahuje implementaci výše zmíněných funkcí a případně implementaci Vámi realizovaných podpůrných funkcí. Odevzdávaný soubor nesmí obsahovat nic jiného, zejména nesmí obsahovat funkci main, vkládání hlavičkových souborů a pod. (takový obsah nejspíše povede k chybě při kompilaci). V testovacím prostředí, kde Váš soubor bude kompilován, jsou vložené hlavičkové soubory iostream, iomanip a fstream. Pro usnadnění odevzdávání a ladění můžete využít toho, že Progtest nastavuje promněnnou preprocesoru __PROGTEST__.

Vzorový příklad

Vstupní data:

{{8,1}, {4,1}, {100,1}, {44,1}, {22,1}, {18,1}, {16,1}, {8,2}, {2,1}, {16,2}, {99,1}, {103,1}, {100,2}, {44,2}, {22,2}, {42,1}, {22,3}, {42,2}, {22,4}, {100,3}, {2,2}};

Seřazená data:

{{2,1}, {2,2}, {4,1}, {8,1}, {8,2}, {16,1}, {16,2}, {18,1}, {22,1}, {22,2}, {22,3}, {22,4}, {42,1}, {42,2}, {44,1}, {44,2}, {99,1}, {100,1}, {100,2}, {100,3}, {103,1}};

Testy a přesuny


Použití přímo ShakerSort na celé pole:
size = 21, tests = 180, moves = 261

Použití přímo SelectSort na celé pole:
size = 21, tests = 210, moves = 127

Použití BucketSort na celé pole:
size = 12, tests = 54, moves = 75 //shakerSort
size = 4, tests = 6, moves = 10 //selectSort
size = 5, tests = 8, moves = 9 //shakerSort
size = 21, tests = 106, moves = 136; //bucketSort