Simple Quick Sort

Collapse Content Show Content

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.

Previous Next Node

Comments

mike

Aug 31, 3:22 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();
}

mike

Aug 31, 4:20 PM

static void doStuff(int[] ar){
partition(ar, 0, ar.length - 1);
}

static void partition(int[] ar, int min, int max){
    int pivot = ar[min];

cont...

    int pivotLocation = min;

    for (int i = min; i <= max; i++){
      int curr = ar[i];
      if(curr < pivot){
        for(int j = i; j > pivotLocation; j--){
          ar[j] =ar[j-1];
        }
        ar[pivotLocation] = curr;
        pivotLocation++;
      }
    }

    if (pivotLocation > min + 1){
      partition(ar, min, pivotLocation-1);
    }

    if ((max - pivotLocation) > 1){
      partition(ar, pivotLocation+1, max);
    }
    printArray(ar, min, max);
}

static void printArray(int[] ar, int min, int max){
    for(int i = min; i <= max; i++){
        System.out.print(ar[i] + " ");
    }

    System.out.println();
}