Quicksort

Just went through the quicksort.  The description is again pretty superficial.   Can't blame the lecturer because quicksort by itself could be quite technical.

There are many variations of quicksort.  The Sedgewick's variation is probably the fastest.   We probably won't go through it. 

There are one good thing about the lecture.  It puts a lot of stress on the partition function.  So one thing I learnt, as it turns out the partition function actually doesn't always divide the array to halves. (!)  It's a very good thing to know.  

Time to implement quicksort once myself.  It's something quite tricky to implement.  Also want to take a look of the analysis of quicksort as well.  Why the average case is nlogn? 

Quicksort

Every programmer knows that quicksort is the most prominent method in sorting.  Saving funny sorting scheme such as bubble or shell, quicksort is also very difficult to be analyzed.  So I decided to read through Chapter 7 of CLRS.   Quicksort would probably take me at least 100-200 practices to fully master because there are just too many possible variations.  Just the original Sedgewick's paper and survey paper would make at least 10 variations possible.

33_P