Binary Search and Quicksort

[simonjtyler]

In the course I teach for 16-18 year old high school students we need to know a few searching and sorting algorithms. Binary search and quicksort are naturally thought of as recursive. Here are a couple of implementations of them that I use with the students:

• Binary search with a simple call structure, but inefficient due to copying data and complicated but having to adjust the indices when the right branch is called during recursion.
• Binary search that works by passing through the indices of the part of the list left to search. (Note: I had to modify this as something about named/default parameters did not work!)
• Simple version of quicksort designed to be clear, but not in-place or efficient.
• Quicksort using the Lomuto partition scheme. It sorts in-place, so is more efficient, but still not optimised!

Thanks for providing this tool Pamela, for recursive functions it complements Python Tutor nicely!

[pamelafox]

So cool, thank you for sharing all your use cases and examples! The sorting algorithms like Quicksort are tricky, we added a few visualizations of them in the Khan Academy articles written by the Dartmouth professors (https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort).