Izziv 3
Napišite program, ki šteje primerjave pri urejanju celoštevilskih tabel z algoritmom Timsort. Uporabite osnovno različico, ki smo jo spoznali na vajah in ki je opisana na prosojnicah in v članku (oboje najdete na Učilnici). Štejte vsako primerjavo, pri kateri je udeležen nek element tabele.
Testiranje:
Za vsak $n$ iz množice ${1, 2, ..., 19}$ in za vsak $k$ iz množice ${0, 1, 2, ..., n-1}$ izdelajte tabelo dolžine $2^n$, sestavljeno iz $2^k$ enako dolgih čet. Vsaka četa naj bo sestavljena iz števil 1, 2, ..., $d$, kjer je $d$ dolžina čete.Izhod:
Na standardni izhod izpišite preglednico oblike
X X X X X X X X X X ... X X ... X
V $i$-ti vrstici in $j$-tem stolpcu naj bo zapisano število primerjav, ki jih vaša implementacija algoritma Timsort opravi na tabeli dolžine $2^i$, sestavljeni iz $2^{j-1}$ čet.
Zelo priporočljiv (četudi neobvezen) dodatek:
V odvisnosti od števila čet primerjajte čas izvajanja vaše implementacije in čas izvajanja privzetega algoritma urejanja, ki ga ponuja programski jezik.
Preverite, ali je vaša implementacija algoritma Timsort stabilna -- denimo tako, da tabelo objektov z atributoma ime in priimek, ki se razlikujejo zgolj po atributu ime, uredite po atributu priimek. Če vaša implementacija ni stabilna, jo ustrezno popravite.