4 ms·
But it has an O(n^2) cost for a particular input Even worse is the fact for naive implementations (such as students might come up with) the worst case behaviou
by chongli 2y ago
But it has an O(n^2) cost for a particular input
Even worse is the fact for naive implementations (such as students might come up with) the worst case behaviour occurs in very common cases such as sorting already sorted lists or reverse-sorted lists.
- ykonstant 2y agoWe have different notions of "covered", then. When I teach algorithms and introduce quicksort, the majority of the time is spent discussing strategies for choosing the pivot. I expect none of my students to implement a quicksort with bad pivot selection; if they do, that's my failure as a teacher and definitely failure in "coverage" of the algorithm.