3 ms·

This is what I do in my introductory data structures and algorithms course at a Bay Area community college: I teach binary search as part of my introduction to

This is what I do in my introductory data structures and algorithms course at a Bay Area community college: I teach binary search as part of my introduction to recursion, and then the following lectures are a series of lessons on sorting algorithms, beginning with selection sort and then insertion sort. After teaching these O(n^2) algorithms, I spend a lecture on merge sort and then have a lecture on quicksort, both for covering O(n lg n) sorts and for introducing my students to divide-and-conquer recursive algorithms.

bee_rider 2y ago
It is a shame that quicksort has to be covered. I mean, it does have to be covered. But it has an O(n^2) cost for a particular input, despite being generally considered nlog(n), seems to me to introduce some fuzziness in an otherwise solid concept. But it does need to be covered. Unfortunately. (Mergesort is best).
- 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 ago
    We 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.
- ncruces 2y ago
  Quicksort is an important, extremely flexible, and very hard to beat unstable comparison sort. It's based on a very simple but powerful idea/strategy (divide & conquer). Its flexibility means it can be adapted to partially sort, find top-N, find the median or any other rank, all optimally. And it's so much faster in practice than everything else (why?), that even after mitigating its worse case, it often comes out ahead. Also, it is relevant/necessary to teach the concept of average, best and worse cases in complexity analysis. What best way to do it than “the best sorting algorithm is terrible for some inputs”? You can also use it to teach/learn adaptive algorithms (you're almost expected too): switch to something else on the base case; or on the worst case; can we do better for low cardinality; etc. So, of course it needs to be covered. There's more to learn from 200 lines of Quicksort than from Mergesort: https://github.com/ncruces/sort/blob/main/quick/quick.go https://github.com/ncruces/sort/blob/main/quick/quick.go
  - Retric 2y ago
    > very hard to beat radix sort If you’re forced to use comparative sorting and write it by hand and it’s near random etc then Quicksort isn’t that bad but even then there’s better options.
    - ncruces 2y ago
      Yes, I said comparison sort. And it is hard to beat, which is why the standard libraries of languages like C++, Rust, Go, C#, Java (etc) use some quicksort variant for their unstable sorts (and some mergesort variant when they need stability). All of the above aren't forced to use comparison sorts, they just do; no other caveats required.
      - Retric 2y ago
        > Yes, I said comparison sort. You mentioned it was a comparisons sort, but not that you were only comparing it with other comparison sorts. There’s also a huge caveat, libraries know less about your data than you do. Thus different default choices become optimal but any decent library will give you many options for very good reasons. Quicksort is relatively terrible for partially ordered lists like appended timestamps from multiple processes etc etc. It’s only ok at a very narrow range of problems, and the important bit isn’t the implementation but where those borders are.
        ncruces 2y ago
        > Quicksort is relatively terrible for partially ordered lists like appended timestamps from multiple processes etc etc. It's not, not really: pdqsort handles those organically. I'm sorry if "best sort", "so much faster" and "very hard to beat" felt like baits. But "huge caveat", "relatively terrible" and being "forced to use comparative sorting" are not fair descriptions of quicksort or why it's used and chosen by standard libraries. Regardless, my point was that there's a lot to learn from quicksort. It's not “a shame” that it must be taught, and mergesort is not “best.”

bee_rider 2y ago

It is a shame that quicksort has to be covered. I mean, it does have to be covered. But it has an O(n^2) cost for a particular input, despite being generally considered nlog(n), seems to me to introduce some fuzziness in an otherwise solid concept. But it does need to be covered. Unfortunately. (Mergesort is best).

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 ago
  We 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.
ncruces 2y ago
Quicksort is an important, extremely flexible, and very hard to beat unstable comparison sort. It's based on a very simple but powerful idea/strategy (divide & conquer). Its flexibility means it can be adapted to partially sort, find top-N, find the median or any other rank, all optimally. And it's so much faster in practice than everything else (why?), that even after mitigating its worse case, it often comes out ahead. Also, it is relevant/necessary to teach the concept of average, best and worse cases in complexity analysis. What best way to do it than “the best sorting algorithm is terrible for some inputs”? You can also use it to teach/learn adaptive algorithms (you're almost expected too): switch to something else on the base case; or on the worst case; can we do better for low cardinality; etc. So, of course it needs to be covered. There's more to learn from 200 lines of Quicksort than from Mergesort: https://github.com/ncruces/sort/blob/main/quick/quick.go https://github.com/ncruces/sort/blob/main/quick/quick.go
- Retric 2y ago
  > very hard to beat radix sort If you’re forced to use comparative sorting and write it by hand and it’s near random etc then Quicksort isn’t that bad but even then there’s better options.
  - ncruces 2y ago
    Yes, I said comparison sort. And it is hard to beat, which is why the standard libraries of languages like C++, Rust, Go, C#, Java (etc) use some quicksort variant for their unstable sorts (and some mergesort variant when they need stability). All of the above aren't forced to use comparison sorts, they just do; no other caveats required.
    - Retric 2y ago
      > Yes, I said comparison sort. You mentioned it was a comparisons sort, but not that you were only comparing it with other comparison sorts. There’s also a huge caveat, libraries know less about your data than you do. Thus different default choices become optimal but any decent library will give you many options for very good reasons. Quicksort is relatively terrible for partially ordered lists like appended timestamps from multiple processes etc etc. It’s only ok at a very narrow range of problems, and the important bit isn’t the implementation but where those borders are.
      - ncruces 2y ago
        > Quicksort is relatively terrible for partially ordered lists like appended timestamps from multiple processes etc etc. It's not, not really: pdqsort handles those organically. I'm sorry if "best sort", "so much faster" and "very hard to beat" felt like baits. But "huge caveat", "relatively terrible" and being "forced to use comparative sorting" are not fair descriptions of quicksort or why it's used and chosen by standard libraries. Regardless, my point was that there's a lot to learn from quicksort. It's not “a shame” that it must be taught, and mergesort is not “best.”