prikaz prve stranice dokumenta Algoritam Timsort
  Preuzmi
PDF 767.62 KB
diplomski rad
Algoritam Timsort
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2019. urn:nbn:hr:217:099092
Beg, Mislav
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Beg, M. (2019). Algoritam Timsort (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:099092

Beg, Mislav. "Algoritam Timsort." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2019. https://urn.nsk.hr/urn:nbn:hr:217:099092

Beg, Mislav. "Algoritam Timsort." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2019. https://urn.nsk.hr/urn:nbn:hr:217:099092

Beg, M. (2019). 'Algoritam Timsort', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 02.10.2024., https://urn.nsk.hr/urn:nbn:hr:217:099092

Beg M. Algoritam Timsort [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2019 [pristupljeno 02.10.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:099092

M. Beg, "Algoritam Timsort", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2019. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:099092

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:099092
Podaci o radu
NaslovAlgoritam Timsort
AutorMislav Beg
MentorVedran Čačić (mentor)
Član povjerenstvaVedran Čačić (predsjednik povjerenstva)
Član povjerenstvaVedran Krčadinac (član povjerenstva)
Član povjerenstvaTomislav Berić (član povjerenstva)
Član povjerenstvaFranka Miriam Bruckler (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2019-03-01, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
Timsort je jedan od najkorištenijih algoritama danas te ga razni programski jezici koriste kao standardni algoritam za sortiranje. U uvodnom dijelu dajemo kratki opis problema sortiranja i uvodimo određene pojmove vezane za sortiranje koji nam koriste da bismo lakše raspravljali o svojstvima Timsorta. Zatim dokazujemo donju granicu za složenost uspoređujućih algoritama i prikazujemo povijest algoritama za sortiranje, te neke od njih detaljnije opisujemo. Glavni dio rada se sastoji od ilustriranja načina rada i dokaza složenosti Timsorta. Prvo opisujemo kako radi algoritam, zatim na izvornom kodu detaljno objašnjavamo sve funkcije i svaki korak algoritma. Na kraju dajemo dokaz \(\mathcal{O}(n\log n)\) složenosti Timsorta, što je najbolja moguća složenost za uspoređujuće algoritme.
Sažetak (engleski)
Timsort is one of the most widely used algorithms today. For many programming languages it is the standard sorting algorithm used. In the introductory part a short description of the problem of sorting is presented and we introduce certain definitions related to sorting that help us discuss some of Timsort’s properties. We then provide a proof of the lower bound for the complexity of comparison sort algorithms and present the history of sorting algorithms, some of which we explain in further detail. The main part of the thesis is comprised of illustrating the sorting process of Timsort and a proof of its complexity. First, we describe how the algorithm works. Then, using the source code, we explain in further detail all the functions and every step of the algorithm. Lastly, we provide a proof for Timsort’s \(\mathcal{O}(n\log n)\) complexity, which is the best possible for comparison sort algorithms.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:099092
Studijski programNaziv: Računarstvo i matematika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2019-07-10 09:49:02