Skip to main content
Učilnica FRI 24/25
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Učilnica FRI 24/25
Home
Expand all Collapse all
  1. aps2uni
  2. 17. marec -- 23. marec
  3. Izziv 3

Izziv 3

Completion requirements
Due: Sunday, 30 March 2025, 11:59 PM

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.

You are currently using guest access (Log in)
Get the mobile app
Powered by Moodle
Obvestilo o avtorskih pravicah