Skip to main content
Učilnica FRI 23/24
  • Home
  • More
Close
Toggle search input
English ‎(en)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
You are currently using guest access
Log in
Home
Course Activities
Assignments Forums Quizzes Resources
Recent Courses
You are not enrolled in any courses
  1. aps2uni
  2. Izziv 3

Izziv 3

Completion requirements
Due: Sunday, 24 March 2024, 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.

◄ Kviz 3
04-Dual-Pivot Quicksort ►
You are currently using guest access (Log in)
Get the mobile app Obvestilo o avtorskih pravicah
Powered by Moodle