Malý domácí úkol z šestého cvičení
Implementujte funkci mySort(array) : [Int] → [Int], která na výstup vrátí speciálně setříděné pole
array. Pole speciálně setřiďte algoritmem insert sort. Speciální třídění spočívá v tom, že všechna
sudá čísla budou před všemi lichými čísli a lichá i sudá čísla budou setříděná podle velikosti. Takto
máte čísla setřídit během algoritmu, rozhodně tedy nemáte pole rozdělit do dvou menších polí
lichých a sudých čísel, ta setřídit zvlášť a nakonec je spojit. Neměňte vstupní pole, ve funkci si
udělejte jeho kopii.
Příklad:
mySort([3,8,1,4,5,9,2,7,6]) → [2,4,6,8,1,3,5,7,9]
Jak funguje insert sort:
Na začátku je první prvek pole setříděný a zbytek pole je zamíchaný. Posunujeme druhý prvek
doleva, dokud se nedostane na místo, kam patří. Teď už jsou setřídené první dva prvky pole a
zbytek je zamíchaný. Posunujeme třetí prvek doleva, dokud se nedostane na místo kam patří. Teď
už jsou setříděné první tři prvky pole. Posunujeme čtvrtý prvek doleva…
Optimalizace:
Při posouvání prvku doleva není potřeba přesouvaný prvek vkládat na každé uvolněné místo, stačí
si jej uložit bokem, přesunout ostatní prvky, a pak jej vložit až na místo, kam opravdu patří.