QuickSort1


Collapse Content

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.

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

  • Your output partitions about the value at the LEFT of the array, not the RIGHT as specified in the challenge description

  • Can anyone tell me what is the problem with the code:

    static void doStuff(int[] ar){
        int pivotValue, storeIndex;
        int left = 0; int right = ar.length - 1;
    
    cont...
  • In this challenge, note the elements should otherwise remain in the same order (see correct output).

  • 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?

  • I've solved it, but in a not too efficient way:

    static void doStuff(int[] ar){
        int pivotValue;
    
        int left = 0; int right = ar.length - 1;
    
    cont...
  • After getting it correct, you can view the featured answer(s) for a possible solution:
    http://www.learneroo.com/modules/4/nodes/44/featured-submissions

    (The sort only becomes efficient in Quick-Sort Advanced.)

  • correct answer for the first input should be 3 1 4 9 5

    public static int partition(int[] a, int lo, int hi) {
        int i = lo + 1;
        int j = hi;
    
    cont...
  • 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.

Contact Us
Sign in or email us at [email protected]