I made some blocks that do generic-comparator bubble-sort and quick-sort, and report #comparisons, #swaps, which I think are pretty cool, and could be useful for a BJC/CSP/other class.
Here is the link, the comments describe some experiments that students can do, not to mention examining the code to understand the algorithms (you have to go to the editor and play with the blocks on the script page)
You can export the blocks and import them to use them in another sheet. For instance here the quicksort is used to sort the contact list for BJC U3L2:
Hmm... let me try. <iframe allowfullscreen allow="geolocation; microphone; camera" frameBorder=0 src="https://snap.berkeley.edu/embed?project=U3L2-ContactList%2BSort&user=ruberad&showTitle=true&showAuthor=true&editButton=true&pauseButton=true" width="480" height="390"></iframe>
The plus sign needs to be encoded; replace it with %2B and it will work.
Interesting. We used to compare an n^2 sort with an n log n sort in Unit 5, where we do analysis of algorithms. That's one of the things we lost to meet teachers' complaints that there's too much in the curriculum, and that the sort algorithms are hard to teach, but I'd like to bring sorting back, at least as an optional project. I think U3 is a little early for it; among other reasons, we prefer to do exclusively functional programming on lists in the early units rather than getting into swapping items in place. So if we were going to put a partition sort (that's the generic term for quicksort-like things) in U3 I'd do it this way:
I picked the base case test I did because I'm imagining a linked list, for which LENGTH is O(n). This algorithm has a relatively high constant factor because it traverses the entire list three times, one for each KEEP. It also does redundant comparisons. Still, it's O(n log n), and it has the pedagogic virtue of being easy to understand and easy to get right (unlike the quicksort business of two pointers moving toward each other, which is prone to off-by-one errors).
But I much prefer mergesort, which is super elegant (imho, ymmv).
By the way, I was taught that it's not Quicksort unless it has all the bells and whistles, such as using median(first, last, middle) as the pivot (to guard against data coming in already sorted) and switching to insertion sort when n<6 or thereabouts, because for small n the asymptotic order of growth is swamped by the way smaller constant factor.
For some reason bubble sort gives me a headache; it took decades for me to convince myself that it actually works. I'm not suggesting that anyone else's teaching should suffer for my peculiarity about this. :~) But I like insertion sort, because it's nearly linear time when the data are largely in order, as happens, for example, when inserting today's new data into yesterday's sorted database.
PS One virtue of my partition sort is that it's stable, unlike Quicksort.
Thx for the detailed response, all great points of course. That partition sort is indeed prettier (and Snap!pier -- who would expect anything less from bh?) than my ghetto quicksort.
My thoughts on curriculum: You've got Contact List in U3, then there's linear/binary search in U5L1 (I'm guessing that's what's left after n^2/nlogn sorting got cut?) naive vs decent sorting could be put in as either an 'If there's time' or 'Taking it Further' in U5L1 (and why not apply it to Contact List? I think students will naturally feel the awkwardness of the Contact List being unsorted, even if they don't explicitly say so). Or maybe an optional project in U5, like the earlier units have optional projects. It's also a nice example for the utility of being able to pass in a function to make sorting generic.
lol hit the 24hr comment cap for new users so I can't comment elsewhere, but I bet I can edit this one!
FWIW I'm doing BubbleSort/QuickSort day 1, by manually sorting playing cards. 2-person teams, one executes the algorithm and calls out COMP or SWAP, the other watches and tabulates. Repeat for 6/12/24/36/48 cards, repeat for Bubble/Quick. Partners swap roles every time. Enter data into spreadsheet, graph and analyze.
EDIT2: U8L2 is Selection vs Partition, although not with the detail of n^2 vs nlogn. Note Bubble Sort is just Selection sort (always selecting for the maximum not the minimum) real-time instead of pulling it out at the end of the pass. OR, you could have bubble-sort passes find the minimum running back to front to make it more like selection. And Selection sort is kind of inside-out Insertion sort.
This isn't the simplest possible way to write SPLIT, but it's super efficient for linked lists, making only one pass through the input, so O(n) with a small constant factor.
It take about 1 seconds to générate 1000 records
It take about 8 seconds to shuffle these records
With QUICK SORT, it take about 2 seconds to sort these records And fun fact, if you sort again the records with quick sort, it take 5 seconds (3 more seconds to sort records already sort)
Sorry for dig up this old topic and my bad english i love to see sorting algorythm
