Clément Canonne📊 It's Friday here (and Thursday elsewhere for many: you know who you are!), time for a (bi)weₐᵉkly quiz!
Today, let's do something simple, just to get our affairs in order: sorting! #weaeklyquiz
1/6
You have n numbers, say, and you want to sort them. Classic stuff. You also took Algorithms and Data Structures, or Data Structures and Algorithms, or Datarithms and Agriculture,* so you know what to do.
Sorting algorithms! But which one to use?
* 👀
2/6
First of all, erm...
Q1: which one of these sorting algorithms does *not* actually exist (yet)?
3/6
Bubble Sort 🫧
Pancake Sort 🥞
Flip Sort 🩴
Shell Sort 🐚
Poll ended at .
Well, you've got to choose which sorting algo to use. Let's focus on worst-case performance, shall we, as one typically does when learning about sorting algorithms in a theory of algos class.
Q2: What's the best worst-case time complexity one can hope for to sort n numbers?
4/6
O(n log n)
O(n)
O(n²)
It depends!
Poll ended at .
(You may notice I am not including the option "Show me the answers" this time. Gotta commit!)
Now, you know, we learn heapsort, merge sort, bubblesort 🫧 and then we learn about quicksort, and we all love quicksort. 😍
Q3: what's the worst-case time complexity of QuickSort? 🤔
5/6
O(n log n)
O(n)
O(n²)
Something else!
Poll ended at .
I'll stop here, for once, and keep it actually short. Beware though, it's only 3 questions, but at least one is a trap!
(Too late. 🙃)
As usual, answers and discussions next week, in ≈3 days. See you then!
6/end
Answers and discussion for last week's 📊(bi)weₐᵉkly quiz on sorting! "Given n numbers as input, sort those numbers."
How hard can it be? What algorithm to use?
[Sorry for the delay, and keeping it short (I am a little under the weather).]
1/11
We have a bazillion sorting algorithms. I am not kidding — so many! Q1 was asking to spot the one that doesn't exist...
https://mathstodon.xyz/@ccanonne/110115671556951575
Turns out, 49% of you got it right (you're good!): "Flip Sort" (as far as I know) is not an actual algorithm... all the others? Yes! 🤯
2/
Clément Canonne (@[email protected])
First of all, erm... Q1: which one of these sorting algorithms does *not* actually exist (yet)? 3/6 [ ] Bubble Sort 🫧 [ ] Pancake Sort 🥞 [ ] Flip Sort 🩴 [ ] Shell Sort 🐚
🫧 Bubble sort? Sure. https://en.wikipedia.org/wiki/Bubble_sort
🥞 Pancake Sort? Strange way to go, but it does give a sorting algo. https://en.wikipedia.org/wiki/Pancake_sorting#Algorithm
🐚 Shell Sort? Yessir. (Named after Donald Shell.) https://en.wikipedia.org/wiki/Shellsort
And (so many) more! https://en.wikipedia.org/wiki/Sorting_algorithm
3/
Fine. But how good are these sorting algorithms? How fast can we hope for them to run? That's what Q2 asked... Only 29% of you answered correctly: it depends!
https://mathstodon.xyz/@ccanonne/110115675610275371
Of course, Ω(n) (8% of answers) is a lower bound, because you need to at least read all the numbers (or most of them) if you want to sort them, right?
4/
Clément Canonne (@[email protected])
Well, you've got to choose which sorting algo to use. Let's focus on worst-case performance, shall we, as one typically does when learning about sorting algorithms in a theory of algos class. Q2: What's the best worst-case time complexity one can hope for to sort n numbers? 4/6 [ ] O(n log n) [ ] O(n) [ ] O(n²) [ ] It depends!
And Ω(n log n) (55% of answers) is a well-known lower bound for any #sorting algorithm.... which is restricted to only perform *comparisons* between numbers. 😵
But if I allow the #algorithm to do something else?
5/
Then all bets are off! Using the *values* of the numbers, assuming they're bounded by some max value? Enter Radix Sort, Counting Sort, Bucket Sort and friends!
In some other computation models, or using randomization? See, e.g., Thorup's sorting algo (https://dl.acm.org/doi/10.5555/314161.314319)
Assumptions matter! ⚠️
6/
Alright, last question: QuickSort!
We know QuickSort, right?
We learn and teach QuickSort!
We love QuickSort!
QUICKSORT LOVES US!
☺️
... Right?
Q3: what's the worst-case time complexity of QuickSort? 🤔 https://mathstodon.xyz/@ccanonne/110115686463564215
Well, while 67% are "morally right" answering O(n²) worst-case, only 31% are "technically right" answering O(n log n).. Another plot twist! 🤯
7/
Clément Canonne (@[email protected])
(You may notice I am not including the option "Show me the answers" this time. Gotta commit!) Now, you know, we learn heapsort, merge sort, bubblesort 🫧 and then we learn about quicksort, and we all love quicksort. 😍 Q3: what's the worst-case time complexity of QuickSort? 🤔 5/6 [ ] O(n log n) [ ] O(n) [ ] O(n²) [ ] Something else!
That is, QuickSort, as implemented the "natural way" (naive pivot selection), has worst-case time complexity O(n²), though it does quite well in practice.
Randomized QuickSort (uniformly random pivot) still has worst-case time complexity O(n²), though expected O(n log n)...
8/
... *but* technically one could use the median of medians algorithm for pivot selection (O(n)-time approx median): https://en.wikipedia.org/wiki/Median_of_medians
Which leads to a much clunkier, less simple, Frankenstein-monster-type of a QuickSort... running in worst-case time O(n log n).
Yep!
9/
Of course, nobody uses that in practice because that added clunkiness and complexity pretty much defeats the purpose of QuickSort, and might as well use HeapSort or Mergesort at this point. But still. IT'S ALIVE! 🧟
I know. Technically, it's Frankenstein's QuickSort *monster.* Frankenstein is the algorithm designer.
10/
Anyway, that's all for this week. I hope it was worth the wait, and that I convinced you there was so much more fun to have, even in something as simple and heavily taught and studied as sorting #algorithms...
Please write questions and comments below, and see you next week! #weaeklyquiz
11/end