A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms

International audienceWe describe a general framework for realistic analysis of sorting and searchingalgorithms, and we apply it to the average-case analysis of five basic algorithms: threesorting algorithms (QuickSort, InsertionSort, BubbleSort) and two selection algorithms(QuickMin and SelectionMin). Usually, the analysis deals with the mean number of keycomparisons, but, here, we view keys as words produced by the same source, which arecompared via their symbols in the lexicographic order. The “realistic” cost of the algorithmis now the total number of symbol comparisons performed by the algorithm, and, in thiscontext, the average–case analysis aims to provide estimates for the mean number ofsymbol comparisons used by the algorithm. For sorting algorithms, and with respectto key comparisons, the average-case complexity of QuickSort is asymptotic to 2n log n,InsertionSort to n2/4 and BubbleSort to n2/2. With respect to symbol comparisons,we prove that their average-case complexity becomes (n log2 n),(n2),(n2 log n). Forselection algorithms, and with respect to key comparisons, the average-case complexityof QuickMin is asymptotic to 2n, of SelectionMin is n − 1. With respect to symbolcomparisons, we prove that their average-case complexity remains (n). In these fivecases, we describe the dominant constants which exhibit the probabilistic behaviour of thesource (namely, entropy, and various notions of coincidence) with respect to the algorithm