Analyse réaliste d'algorithmes standards

Abstract : At first, we were interested in TimSort, a sorting algorithm which was designed in 2002, at a time where it was hard to imagine new results on sorting. Although it is used in many programming languages, the efficiency of this algorithm has not been studied formally before our work. The fine-grain study of TimSort leads us to take into account, in our theoretical models, some modern features of computer architecture. In particular, we propose a study of the mechanisms of branch prediction. This theoretical analysis allows us to design variants of some elementary algorithms (like binary search or exponentiation by squaring) that rely on this feature to achieve better performance on recent computers. Even if uniform distributions are usually considered for the average case analysis of algorithms, it may not be the best framework for studying sorting algorithms. The choice of using TimSort in many programming languages as Java and Python is probably driven by its efficiency on almost-sorted input. To conclude this dissertation, we propose a mathematical model of non-uniform distribution on permutations, for which permutations that are almost sorted are more likely, and provide a detailed probabilistic analysis
Document type :
Theses
Complete list of metadatas

Cited literature [38 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-02085819
Contributor : Abes Star <>
Submitted on : Sunday, March 31, 2019 - 7:15:07 PM
Last modification on : Tuesday, May 21, 2019 - 12:36:35 AM
Long-term archiving on : Monday, July 1, 2019 - 12:31:13 PM

File

TH2018PESC1110.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-02085819, version 1

Collections

Citation

Nicolas Auger. Analyse réaliste d'algorithmes standards. Informatique et langage [cs.CL]. Université Paris-Est, 2018. Français. ⟨NNT : 2018PESC1110⟩. ⟨tel-02085819⟩

Share

Metrics

Record views

150

Files downloads

54