0
$\begingroup$

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!

$\endgroup$
  • 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 Filmus Dec 21 '17 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 De Dec 21 '17 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 Filmus Dec 21 '17 at 18:26
  • $\begingroup$ Check out Sedgewick's books. $\endgroup$ – Raphael Dec 21 '17 at 18:40
1
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

Here's a cheat sheet for numerous algorithm implementations and their Average, Best, Worst case notations for Time/Space complexity for future reference. More so implementation of QS.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.