 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

QuickSort1  Simple Quick Sort
 QuickSort 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
QuickSort Advanced
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 "inplace" version of Quicksort, where the numbers are all sorted within the array itself.
Challenge
Create an inplace version of Quicksort. This time, always select the last element in the 'subarray' 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.
Guideline
Instead of copying the array into multiple subarrays, use indices to keep track of the different subarrays. You can pass the indices to a modified partition method. The partition method should partition the subarray 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 subarrays 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.
Click for More
Challenge
Create an inplace QuickSort and Print the entire array on a new line at the end of every partitioning method
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
Comments
Kendall Ponder
Jun 23, 6:52 PMShouldn't the correct output on the first line be 1 3 2 5 9 8 7? The 8 comes before the 7 in the input.
Learneroo
Jun 23, 7:41 PM@Kendall, in this version of Quicksort, you don't move numbers that are already in their correct half. Since 7 > 5 (the pivot value), it stays where it is.
Kendall Ponder
Jun 24, 9:44 AMGot it. Is this method faster than using nested for loops and finding the smallest number in the inner loop and then switching it with the left most element (the outer loop moves where the left most element is)?
Learneroo
Jun 24, 9:57 AMQuicksort is among the fastest sorts in the average case. Technically, it runs in O(n log n) time (see the next Node for a brief look at it's running time). I'm not sure what you're describing, but it sounds like a Selection Sort which would have a O(n^{2)} running time (like Insertion Sort).
Example:
You have 1M numbers to sort. Quicksort takes ~ O(n log n) time which is 1M*log(1M) =~ 20M operations.
Insertion or Selection Sort would take O(n^{2)} time which is 1M^{2} or 10^{12} operations.
Kendall Ponder
Jun 24, 1:21 PMThanks. The way I have sorted before is:
for(I=0 to end)
min=array(I)
minIndex=i
for(j=I to end)
if(array(I)<min)
Switch array(I) & min and save minIndex
end if
end for
end for
Kendall Ponder
Jun 24, 1:22 PMThanks!