Towards a Realistic Analysis of Some Popular Sorting Algorithms. (11th December 2014)

• Record Type: Journal Article
• Authors: CLÉMENT, J.; NGUYEN THI, T. H.; VALLÉE, B.
• Editors: Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 1(2015:Jan.)
• Page Start: 104
• Page End: 144
• Publication Date: 2014-12-11
• Subjects: Primary 68W32, -- 68P10, -- 68P05, -- 68W40, -- 68Q25, -- 68Q87, -- 68Q17, -- Secondary 68W05, -- 94A15, -- 94A17, -- 97I80, -- 30D10, -- 30E15, -- 30E20; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000649
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : We describe a general framework for realistic analysis of sorting algorithms, and we apply it to the average-case analysis of three basic sorting algorithms ( QuickSort, InsertionSort, BubbleSort ). Usually the analysis deals with the mean number of key comparisons, but here we view keys as words produced by the same source, which are compared via their symbols in lexicographic order. The 'realistic' cost of the algorithm is now the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons used by the algorithm. For sorting algorithms, and with respect to key comparisons, the average-case complexity of QuickSort is asymptotic to 2 n log n, InsertionSort to n 2 /4 and BubbleSort to n 2 /2. With respect to symbol comparisons, we prove that their average-case complexity becomes Θ ( n log 2 n ), Θ( n 2 ), Θ ( n 2 log n ). In these three cases, we describe the dominant constants which exhibit the probabilistic behaviour of the source (namely entropy and coincidence) with respect to the algorithm.