- 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
Simple Quick Sort
In the previous challenge, you wrote a 'partition' method to split an array into smaller and greater elements. This means you 'sorted' half the array with respect to the other half. Can you repeatedly use 'partition' to sort an entire array?
Guideline: In Insertion sort, you simply went through each element in order and inserted it into a sorted sub-array. In this challenge, you cannot focus on one element at a time, but instead must deal with whole sub-arrays. Each time you call partition, you are sorting two parts of the array with respect to each other. Notice if you called partition on two elements, that sub-array would be fully sorted.
Can you repeatedly call partition on each sub-array so that the entire array ends up sorted?
Click for More
Challenge
Can you code a Quicksort algorithm?
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
Comments
mike
Aug 31, 3:22 PMmike
Aug 31, 4:20 PMstatic void doStuff(int[] ar){
partition(ar, 0, ar.length - 1);
}