Contributing other sorting algorithms?

Stream: CSLib

[Harry Goldstein]

I have a couple of students who may want to make small (relatively beginner) CSLib contributions over the next few months. I was thinking I could have them contribute a couple of sorting algorithms (e.g., insertion sort), and associated time complexity proofs, in the style of the merge sort example. Would that kind of thing be accepted as a contribution (assuming I worked with the students to make sure everything was styled and set up correctly)?

[Eric Wieser]

I think there are at least 4 PRs that contribute insertionSort in some form, so probably another one is not that helpful a contribution

[Eric Wieser]

I'm not sure I've seen one for bubble sort anyway though

[Harry Goldstein]

Oh I see. I had looked through the issues but not the PRs. Fair enough. I can look for other sorting algorithms and similar CS 1 or CS 2 style algorithms. Also happy to take suggestions for other things that seem relatively easy but that no one currently has the appetite to tackle.

[Ching-Tsun Chou]

Perhaps it would be interesting to formalize some non-comparison sort algorithms like radix sort.

[Chris Henson]

Yes, I unfortunately don't think the issues have much at the moment that is great for beginners. Many of them are me leaving a paper trail of technical chores. I think it would be fine to work on some sorting algorithm other than insertion sort.

[Shreyas Srinivas]

@Harry Goldstein : I’d like to see a binary search algorithm for lists on top of the Prog model in PR cslib#372. It can use the ListSearch model.

[Shreyas Srinivas]

It’s not too difficult, but still hard enough for new students learning lean.

[Shreyas Srinivas]

I’d also recommend quicksort, though in this case I would also suggest using a model similar to SortOpsCmp, but using Vectors, and changing the cmpLT query to compare an argument against a given index of the vector.

[Shreyas Srinivas]

So that’s slightly harder and requires students to think about what is being counted carefully.

[Shreyas Srinivas]

I would even suggest selection sort on Vectors. That should be much simpler than quicksort