- Introduction to Challenges
- Insertion Sort 1
- Insertion Sort Itself
- Correctness and the Loop Invariant
- Running Time
Counting Sort 1
- Simple Counting Sort
- Prepare for Full Counting Sort
- The Full Counting Sort
- Simple Quick Sort
- Quick-Sort Advanced
- Quick Sort Running Time
Input Format for standard Sorting Challenges:
- t - the number of test cases
- s - the size of the array
- ar - the list of integers
The previous version of Quicksort was easy to understand, but it was not optimal. It required copying the numbers into other arrays, which takes up more space and time. To make things faster, one can create an "in-place" version of Quicksort, where the numbers are all sorted within the array itself.
Create an in-place version of Quicksort. This time, always select the last element in the 'sub-array' as a pivot. Partition the left side and then the right side of the array. Print out the whole array at the end of every partitioning method.
Instead of copying the array into multiple sub-arrays, use indices to keep track of the different sub-arrays. You can pass the indices to a modified partition method. The partition method should partition the sub-array and then return the index location where the pivot gets placed, so you can then call partition on each side of the pivot.
Since you cannot just create new sub-arrays for the elements, Partition will need to use another trick to keep track of which elements are greater and which are smaller than the pivot.