IMAGe Brown Bag- The Quicksort Probability Distribution

06/23/2016 - 12:00pm to 1:00pm
ML Chapman Room

Lee Richardson

Carnegie Mellon University

Quicksort is arguably the fastest, most widely used algorithm for sorting an array of numbers. The performance of quicksort is typically measured by the number of comparisons, and it's well known that the average number of comparisons is O(n ln(n)). From a statistical perspective, an interesting aspect of quicksort is that it's a random algorithm. In particular, the number of comparisons depends on the initial permutation of the array. In this talk, I'll discuss an exact solution for the probability distribution, given by Eddy and Schervish. The downside of the exact solution is that it takes O(n^6) time to compute, and we'll discuss an approach for reducing this to O(n^5). Given the performance of the exact calculation, an asymptotic approximation of the distribution will be useful for large n. We discuss the form of the asymptotic distribution, and some for approximating its density. However, the exact distribution is still unknown. This is work in progress, and I'm very interested in ideas and feedback on different approaches.

Thursday, June 23, 2016
12:00 pm - 1:00 pm
Mesa Lab, Chapman Room
(Bring your lunch)