 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
QuickSort1
Insertion Sort is a simple algorithm that works well on small inputs, but its too slow for largescale 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.
Challenge
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.
Input/Output
The Input is similar to the previous challenges. Output the correctly partitioned array.
Challenge
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.
Comments
Rod
Nov 18, 1:41 PMYour output partitions about the value at the LEFT of the array, not the RIGHT as specified in the challenge description
Viktor Ayadi
Aug 7, 8:51 AMCan 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?
Learneroo
Aug 7, 10:41 AMIn this challenge, note the elements should otherwise remain in the same order (see correct output).
Viktor Ayadi
Aug 8, 7:46 AMThank 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 Ayadi
Aug 8, 8:07 AMI've solved it, but in a not too efficient way:
I think the previous algorithm is much more efficient.
Learneroo
Aug 8, 10:04 AMAfter getting it correct, you can view the featured answer(s) for a possible solution:
http://www.learneroo.com/modules/4/nodes/44/featuredsubmissions
(The sort only becomes efficient in QuickSort Advanced.)
Ankit
Mar 16, 7:46 PMcorrect answer for the first input should be 3 1 4 9 5
Learneroo
Mar 16, 7:50 PMSince 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.