{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,24]],"date-time":"2022-04-24T06:40:17Z","timestamp":1650782417713},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,12,11]],"date-time":"2014-12-11T00:00:00Z","timestamp":1418256000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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 (<jats:italic>QuickSort<\/jats:italic>,<jats:italic>InsertionSort<\/jats:italic>,<jats:italic>BubbleSort<\/jats:italic>). 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 \u2018realistic\u2019 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<jats:italic>QuickSort<\/jats:italic>is asymptotic to 2<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>,<jats:italic>InsertionSort<\/jats:italic>to<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>\/4 and<jats:italic>BubbleSort<\/jats:italic>to<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>\/2. With respect to symbol comparisons, we prove that their average-case complexity becomes \u0398 (<jats:italic>n<\/jats:italic>log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>), \u0398(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>), \u0398 (<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>log<jats:italic>n<\/jats:italic>). 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.<\/jats:p>","DOI":"10.1017\/s0963548314000649","type":"journal-article","created":{"date-parts":[[2014,12,11]],"date-time":"2014-12-11T12:23:24Z","timestamp":1418300604000},"page":"104-144","source":"Crossref","is-referenced-by-count":1,"title":["Towards a Realistic Analysis of Some Popular Sorting Algorithms"],"prefix":"10.1017","volume":"24","author":[{"given":"J.","family":"CL\u00c9MENT","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. H.","family":"NGUYEN THI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"VALL\u00c9E","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,12,11]]},"reference":[{"key":"S0963548314000649_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00281-M"},{"key":"S0963548314000649_ref5","first-page":"295","volume-title":"Papers Presented at the the March 3\u20135, 1959, Western Joint Computer Conference","author":"De La Briandais","year":"1959"},{"key":"S0963548314000649_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548314000649_ref24","doi-asserted-by":"crossref","unstructured":"Seidel R. (2010) Data-specific analysis of string sorting. In Proc. 21st Annual ACM\u2013SIAM Symposium on Discrete Algorithms: SODA, pp. 1278\u20131286.","DOI":"10.1137\/1.9781611973075.102"},{"key":"S0963548314000649_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00167-9"},{"key":"S0963548314000649_ref2","unstructured":"Cl\u00e9ment J. , Fill J. , Nguyen Thi T. and Vall\u00e9e B. (2014) Towards a realistic analysis of the QuickSelect algorithm. Theory of Computing Systems, special Issue \u201cSTACS 2013\u201d (Anca Muscholl and Martin Dietzfelbinger)."},{"key":"S0963548314000649_ref22","first-page":"199","volume-title":"Proc. 8th International Conference Words 2011","author":"Roux","year":"2011"},{"key":"S0963548314000649_ref25","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032770"},{"key":"S0963548314000649_ref17","first-page":"490","article-title":"Trie memory","volume":"3","author":"Fredkin","year":"1960","journal-title":"Commun. Assoc. Comput. Mach."},{"key":"S0963548314000649_ref20","volume-title":"Collection de Monographies sur la Th\u00e9orie des Fonctions","author":"N\u00f6rlund","year":"1929"},{"key":"S0963548314000649_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679623"},{"key":"S0963548314000649_ref1","doi-asserted-by":"crossref","unstructured":"Cesaratto E. and Vall\u00e9e B. Gaussian distribution of trie depth for strongly tame sources. In the special issue of CPC (Combinatorics, Probability and Computing) dedicated to Philippe Flajolet (Cambridge University Press 2015).","DOI":"10.1017\/S0963548314000741"},{"key":"S0963548314000649_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S000186780000639X"},{"key":"S0963548314000649_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679622"},{"key":"S0963548314000649_ref26","unstructured":"Vall\u00e9e B. Rice or Poisson\u2013Mellin? In preparation."},{"key":"S0963548314000649_ref14","doi-asserted-by":"crossref","unstructured":"Flajolet P. , Roux M. and Vall\u00e9e B. (2010) Digital trees and memoryless sources: From arithmetics to analysis. In Proc. AofA'10, DMTCS Proc. AM, pp. 231\u2013258.","DOI":"10.46298\/dmtcs.2799"},{"key":"S0963548314000649_ref19","doi-asserted-by":"crossref","unstructured":"Jacquet P. and Szpankowski W. (1998) Entropy computations for discrete distributions: Towards analytic information theory. In IEEE International Symposium on Information Theory.","DOI":"10.1109\/ISIT.1998.708978"},{"key":"S0963548314000649_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00002-E"},{"key":"S0963548314000649_ref9","first-page":"300","article-title":"The number of bit comparisons used by Quicksort: An average-case analysis","volume":"17","author":"Fill","year":"2004","journal-title":"Proc. ACM\u2013SIAM Symposium on Discrete Algorithms: SODA 2004"},{"key":"S0963548314000649_ref6","doi-asserted-by":"publisher","DOI":"10.2307\/121012"},{"key":"S0963548314000649_ref4","unstructured":"Cl\u00e9ment J. , Nguyen Thi T. and Vall\u00e9e B. (2013) A general framework for the realistic analysis of sorting and searching algorithms: Application to some popular algorithms. In STACS 2013, pp. 598\u2013609."},{"key":"S0963548314000649_ref28","first-page":"750","volume-title":"Proc. ICALP 2009, part I","author":"Vall\u00e9e","year":"2009"},{"key":"S0963548314000649_ref12","unstructured":"Flajolet P. (2008) A journey between Rice, Mellin and Poisson. Personal communication."},{"key":"S0963548314000649_ref11","first-page":"1","volume-title":"Proc. 23rd Annual Symposium on Theoretical Aspects of Computer Science: STACS 2006","author":"Flajolet","year":"2006"},{"key":"S0963548314000649_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385798117431"},{"key":"S0963548314000649_ref23","volume-title":"Algorithms in C, parts 1\u20134","author":"Sedgewick","year":"1998"},{"key":"S0963548314000649_ref8","doi-asserted-by":"publisher","DOI":"10.1214\/12-AAP866"},{"key":"S0963548314000649_ref21","volume-title":"Vorlesungen \u00fcber Differenzenrechnung","author":"N\u00f6rlund","year":"1954"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000649","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,24]],"date-time":"2022-04-24T06:17:06Z","timestamp":1650781026000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000649\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,11]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["S0963548314000649"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000649","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,11]]}}}