, Algorithme de tri optimal pour la mesure m rec, p.163
, 166 6.4.1 L'arbre de génération pour la distribution d'Ewens classique166 6, vol.4
,
, Conclusion et perspectives 204
,
, Modèle d'Ewens
, 166 6.4.1 L'arbre de génération pour la distribution d'Ewens classique
, Générateur linéaire pour la distribution d'Ewens
, Générateur linéaire pour la distribution d'Ewens gé-néralisée aux records
, Étude de la distribution d'Ewens généralisée aux records
,
, , p.190
, Espérances et asymptotiques des différentes statistiques
,
, Lemme 18 de décomposition qui nous a été fort utile pour démontrer de nombreux résultats sous la distribution d'Ewens généralisée au nombre de records. Nous pourrions, à l'instar des développeurs de Java, faire une série de benchmarks pour obtenir des statistiques sur les séquences d'entrée couramment utilisées lors de l'appel des fonctions de tris dans l'industrie. Pour y parvenir, il nous faudrait potentiellement établir des partenariats avec des entreprises dans le but de pouvoir utiliser des espions qui feraient des analyses sur ces entrées. À l'aide de ces statistiques, nous pourrions comparer nos distributions non-uniformes avec un échantillon des véritables distributions, La difficulté vient du fait qu'il n'est plus possible d'utiliser le
, Listing 7 -Simulation l'algorithme d'exponentiation rapide guidé. Ce script met en évidence les constantes ? calculé à partir du Théorème 10
,
,
, Librairie papi performance application programming interface
, The microarchitecture of intel, amd and via cpus
, 5th jilp workshop on computer architecture competitions (jwac-5) : Championship branch prediction, p.5, 2016.
, Logarithmic combinatorial structures : a probabilistic approach, European Mathematical Society, vol.1, 2003.
,
, Analysis of algorithms for permutations biased by their number of records, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01838692
, On the Worst-Case Complexity of TimSort, of Leibniz International Proceedings in Informatics (LIPIcs), vol.112, pp.1-4, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01798381
, Merge Strategies : from Merge Sort to TimSort, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01212839
, Good Predictions Are Worth a Few Comparisons, Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), vol.47, pp.1-12, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01212840
, An experimental study of sorting and branch prediction, Journal of Experimental Algorithmics, vol.12, p.1, 2008.
, An experimental study of sorting and branch prediction, J. Exp. Algorithmics, vol.12, issue.1, p.39, 2008.
, Combinatorics of permutations, 2012.
, On the adaptiveness of quicksort, J. Exp. Algorithmics, vol.12, issue.3, p.20, 2008.
, Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms, Algorithms and Data Structures, vol.3608, pp.385-395, 2005.
, Tradeoffs between branch mispredictions and comparisons for sorting algorithms, WADS, pp.385-395, 2005.
, Skewed binary search trees, ESA, pp.708-719, 2006.
, Skewed Binary Search Trees, Algorithms -ESA 2006, vol.4168, pp.708-719, 2006.
, Time bounded random access machines, Journal of Computer and System Sciences, vol.7, issue.4, pp.354-375, 1973.
, , 1994.
, Openjdk's java. utils. collection. sort () is broken : The good, the bad and the worst case, International Conference on Computer Aided Verification, pp.273-289, 2015.
, Branch Mispredictions Don't Affect Mergesort, Experimental Algorithms, vol.7276, pp.160-171, 2012.
, The sampling theory of selectively neutral alleles. Theoretical population biology, vol.3, pp.87-112, 1972.
, Asymptotic behavior of some statistics in ewens random permutations, Electronic Journal of Probability, vol.18, 2013.
, Analytic combinatorics. cambridge University press, 2009.
URL : https://hal.archives-ouvertes.fr/inria-00072739
, On the cycle structure of mallows permutations, The Annals of Probability, vol.46, issue.2, pp.1114-1169, 2018.
, Computer Architecture, Fifth Edition : A Quantitative Approach, 2011.
, How Branch Mispredictions Affect Quicksort, Algorithms -ESA 2006, vol.4168, pp.780-791, 2006.
, The Art of Computer Programming, vol.1, 1997.
, Sorting and searching, vol.3, 1998.
, The influence of caches on the performance of sorting, Journal of Algorithms, vol.31, issue.1, pp.66-104, 1999.
, Markov Chains and Mixing Times, 2008.
, Measures of presortedness and optimal sorting algorithms, IEEE transactions on computers, vol.100, issue.4, pp.318-325, 1985.
, Analysis of branch misses in quicksort, Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, pp.114-128, 2015.
, Optimistic sorting and information theoretic complexity, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '93, pp.467-474, 1993.
, Computer Organization and Design, The Hardware/Software Interface, 2013.
, Original notes on timsort, 2001.
, A first look at rigorous probability theory, 2006.
, Improved master theorems for divide-and-conquer recurrences, J. ACM, vol.48, issue.2, pp.170-205, 2001.
, Super scalar sample sort, ESA, vol.3221, pp.784-796, 2004.
, Smoothed analysis of algorithms : Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), vol.51, issue.3, pp.385-463, 2004.