4 ms·

Agreed, WRT the bigger picture; lots of little algorithms could come before binary search. But, giving them binary search before sorting kinda works. It is mot

Agreed, WRT the bigger picture; lots of little algorithms could come before binary search. But, giving them binary search before sorting kinda works. It is motivating. If you do sorting first, it just seems like a weird high-effort excursion into a niche bookkeeping thing about lists. Once they see how fast binary search is (just give them pre-sorted lists to run it on), sorting becomes interesting, right?

kadoban 2y ago
Yeah, it does work as something you learn with/right-before/right-after a sorting algorithm, depending on the teaching style.
linguae 2y ago
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.

kadoban 2y ago

Yeah, it does work as something you learn with/right-before/right-after a sorting algorithm, depending on the teaching style.

linguae 2y ago

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.