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 :
Complete list of metadatas
Contributor : Abes Star <>
Submitted on : Sunday, March 31, 2019 - 7:15:07 PM
Last modification on : Tuesday, May 21, 2019 - 12:36:35 AM


Version validated by the jury (STAR)


  • HAL Id : tel-02085819, version 1



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



Record views


Files downloads