- 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
- 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
Quick-Sort 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 "in-place" version of Quicksort, where the numbers are all sorted within the array itself.
Challenge
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.
Guideline
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.
Click for More
Challenge
Create an in-place 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(n2) 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(n2) time which is 1M2 or 1012 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!