Quick-Sort Advanced


Collapse Content

The previous version of Quicksort was easy to understand, but it was not optimal. It required copying the numbers into other arrays, which takes up more space and time. To make things faster, one can create an "in-place" version of Quicksort, where the numbers are all sorted within the array itself.

Challenge
Create an in-place version of Quicksort. This time, always select the last element in the 'sub-array' as a pivot. Partition the left side and then the right side of the array. Print out the whole array at the end of every partitioning method.

Guideline
Instead of copying the array into multiple sub-arrays, use indices to keep track of the different sub-arrays. You can pass the indices to a modified partition method. The partition method should partition the sub-array and then return the index location where the pivot gets placed, so you can then call partition on each side of the pivot.

Since you cannot just create new sub-arrays for the elements, Partition will need to use another trick to keep track of which elements are greater and which are smaller than the pivot.

Click for More

Challenge

Create an in-place QuickSort and Print the entire array on a new line at the end of every partitioning method

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Comments

  • Shouldn't the correct output on the first line be 1 3 2 5 9 8 7? The 8 comes before the 7 in the input.

  • @Kendall, in this version of Quicksort, you don't move numbers that are already in their correct half. Since 7 > 5 (the pivot value), it stays where it is.

  • Got it. Is this method faster than using nested for loops and finding the smallest number in the inner loop and then switching it with the left most element (the outer loop moves where the left most element is)?

  • Quicksort is among the fastest sorts in the average case. Technically, it runs in O(n log n) time (see the next Node for a brief look at it's running time). I'm not sure what you're describing, but it sounds like a Selection Sort which would have a O(n2) running time (like Insertion Sort).

    cont...
  • Thanks. The way I have sorted before is:
    for(I=0 to end)
    min=array(I)
    minIndex=i
    for(j=I to end)
    if(array(I)<min)
    Switch array(I) & min and save minIndex
    end if
    end for
    end for

Contact Us