Algoritam Timsort

master's thesis

• Author: Mislav Beg
• Mentor: Vedran Čačić (mentor)
• Committee member: Vedran Čačić (predsjednik povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Committee member: Tomislav Berić (član povjerenstva)
• Committee member: Franka Miriam Bruckler (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-03-01, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: Timsort; algoritam za sortiranje
• Keywords (english): Timsort; sorting algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:099092
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-07-10 09:49:02