I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. Now, I need a good source from which I can read it and find the materials which I can include in my presentation. As for my existing knowledge on algorithms, one can assume that I almost know nothing except for "just codes" and nothing at all about their analysis. Any book or materials having rigorous proofs will also do. Any help will be greatly appreciated!
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Unfortunately you cannot present such an analysis in full detail without a basic grasp of probability theory. You can do some handwaving which might be good enough for your class. There are many online sources on the average case analysis of quicksort, and you should be able to find something that fits your background. $\endgroup$– Yuval FilmusDec 21, 2017 at 18:08
-
$\begingroup$ Thanks for the reply.Well I'm a statistics student, so probability( and required math) hopefully won't pose much of a problem! Maybe you can update your suggestion then? $\endgroup$– Shial DeDec 21, 2017 at 18:24
-
1$\begingroup$ Have you tried using your favorite search engine for an average case analysis of quicksort? You can find this analysis in many online lecture notes. $\endgroup$– Yuval FilmusDec 21, 2017 at 18:26
-
$\begingroup$ Check out Sedgewick's books. $\endgroup$– Raphael ♦Dec 21, 2017 at 18:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Given your stats background, you will find the "indicator variable" analysis easier than the solution via recurrence equations. It is based on computing the probability that two elements of given ranks are compared to each other.
The idea is described on the wikipedia page and in more detail in Section 7.4 of Cormen et al. Introduction to Algorithms 3rd edition.
answered Dec 29, 2017 at 12:46