QuickSort1

Collapse Content Show 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.

Previous Next Node

Comments

Rod
Nov 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 Ayadi

Aug 7, 8:51 AM

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...

    pivotValue = ar[left];
    storeIndex = left;

    for (int i = left + 1; i <= right; i++) {
        if (ar[i] < pivotValue) {
            storeIndex++;
            swap(ar, i, storeIndex);
        }
    }

    swap(ar, left, storeIndex);
    printAr(ar);        
}

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 AM

In this challenge, note the elements should otherwise remain in the same order (see correct output).
Viktor Ayadi
Aug 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 Ayadi

Aug 8, 8:07 AM

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...

    int[] tmp = new int[ar.length];
    int i = left + 1, j = 0;

    pivotValue = ar[left];

    for (int i = left + 1; i <= right; i++) 
        if (ar[i] < pivotValue) {
            tmp[j] = ar[i];
            j++;
        }

    tmp[j] = pivotValue; j++;


    for (int i = left + 1; i <= right; i++) 
        if (ar[i] >= pivotValue) {
            tmp[j] = ar[i];
            j++;
        }

    ar = tmp;

    printAr(ar);        
}

I think the previous algorithm is much more efficient.

Learneroo
Aug 8, 10:04 AM

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.)

Ankit

Mar 16, 7:46 PM

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...

    while(i < j) {
        while(a[i] < a[lo]) i++;
        while(a[j] > a[lo]) j--;
        if(i < j) {
          swap(a, i, j);
        }
    }
    swap(a, lo, j);
    return j;
}

public static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

static void doStuff(int[] ar){
    int j = partition(ar, 0, ar.length - 1);
    for(int elem: ar) {
        System.out.print(elem + " ");
    }
    System.out.println();
}

Learneroo
Mar 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.

mike

Aug 31, 3:23 PM

static void doStuff(int[] ar){
    int pivot = ar[0];
    int pivotLocation = 0;
    for(int i = 1; i < ar.length; i++){
        int curr = ar[i];
        if(curr < pivot){

cont...

            for(int j = i; j > pivotLocation; j--){
                ar[j] =ar[j-1];
            }
            ar[pivotLocation] = curr;
            pivotLocation++;
        }
    }
    for (int i=0; i<ar.length; i++){
        System.out.print(ar[i] + " ");
    }
    System.out.println();
}