- 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
Insertion Sort is a simple algorithm that works well on small inputs, but its too slow for large-scale sorting. Instead, algorithms like QuickSort are used, which will be covered in these challenges. The first step of quicksort is to partition an array into two parts.
Given an array 'ar' and a number 'p' in the first cell in the array, can you partition the array so that all elements greater than 'p' are to the right of it and all the numbers smaller than 'p' are to its left?
For example, if given the following as input:
4 5 3 9 1
The first number
4 is the pivot, so you should put the smaller numbers to the left, and the larger to the right, and output:
3 1 4 5 9
The array should otherwise remain in the same order.
The Input is similar to the previous challenges. Output the correctly partitioned array.
Can you write code to partition an array?
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
RodNov 18, 1:41 PM
Your output partitions about the value at the LEFT of the array, not the RIGHT as specified in the challenge description
Viktor AyadiAug 7, 8:51 AM
Can anyone tell me what is the problem with the code:
For the first input it gives back the following output:
1 3 4 9 5
I think this is also correct... Am I right?
LearnerooAug 7, 10:41 AM
In this challenge, note the elements should otherwise remain in the same order (see correct output).
Viktor AyadiAug 8, 7:46 AM
Thank you for your answer. Can you give me a hint, howto modify the code to keep the lower and higher elements in such order?
Viktor AyadiAug 8, 8:07 AM
I've solved it, but in a not too efficient way:
I think the previous algorithm is much more efficient.
LearnerooAug 8, 10:04 AM
After getting it correct, you can view the featured answer(s) for a possible solution:
(The sort only becomes efficient in Quick-Sort Advanced.)
AnkitMar 16, 7:46 PM
correct answer for the first input should be 3 1 4 9 5
LearnerooMar 16, 7:50 PM
Since this is just the first step in quicksort, the array should otherwise remain in the same order. So since the 5 is before the 9 in the input, it should be before the 9 in the output.
mikeAug 31, 3:23 PM