Assignment 4 - Quicksort #34
Description
The most famous sorting algorithm. Invented by Tony Hoare. There is a short interview with him telling his invention of quicksort. Read more about quicksort. We will go over two approaches here. First one is the real implementation of quicksort. Second one is less efficient but functional implementation with filters.
git checkout assignment004 to start.
- Quicksort In-place
- Implement Lomuto's partition algorithm. Remember that you need to guard
swapfrom swapping a location with itself. - Implement Hoare's partition algorithm. Note that if you follow the pseudo code given in Wikipedia, the pivot's final location might not be at the returned index. You can check Sedgewick's Algorithms book for another version. Add more tests when you are done with your implementation.
- By using your
hoarePartition, implement an in-place quicksort. - Read about the Dutch National Flag problem. Your function takes a pivot's index. It should rearrange the elements such that all elements less than pivot come first, followed by elements equal to pivot, followed by elements greater than pivot.
- You can check out how Swift implements
sort. The file is a GYB template which stands for Generate Your Boilerplate. You need to clone the Swift repo, and run./utils/gybon theSort.swift.gybto convert it to actual Swift source code. As you can see, the function is calledintroSort, a hybrid sorting algorithm where quicksort falls back to insertion sort and heap sort.
- Implement Lomuto's partition algorithm. Remember that you need to guard
- Functional quicksort
- This is a rather inefficient but neat solution. Pick a pivot and remove it from the array. Then use
filterto create two arrays: one containing smaller items than the pivot, other one containing the rest. Then call the function on these arrays, and append them to each other with the pivot in the middle.
- This is a rather inefficient but neat solution. Pick a pivot and remove it from the array. Then use
Due date: 27.12.2015