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.