QuickSort partition algorithm

Question

Hi,

I am trying to program the quicksort algorithm from Cormen Algorithm Textbook. Below is my code.

class Quicksort
{
    public void qSort(int[] a, int p, int r)
    {
        if(p<r)
        {
            int q = Partition(a, p,r);
            qSort(a, p, q-1);
            qSort(a, q+1, r);
        }
     }

     private int Partition(int[] a, int p, int r)
     {
         int x = a[r];

         int i = p-1;
         int temp=0;

         for(int j=p; j<r-1; j++)
         {
             if(a[j]<=x)
             {
                 i++;
                 temp = a[i];
                 a[i] = a[j];
                 a[j] = temp;
             }
         }

         temp = a[i+1];
         a[i+1] = a[r];
         a[r] = temp;
         return (i+1);
     }
}

public class QuickSortTest
{
     public static void main(String[] args)
     {
         Quicksort qsort = new Quicksort();
         int[] array = {5, 4, 7, 2, 1, 9, 3, 6, 10, 8};

         System.out.print("Original  Array : ");
         for(int i=0; i<array.length;i++)
         {
             System.out.print(array[i] + " ");
         }

         int length = array.length;

         qsort.qSort(array, 0, length-1);

         System.out.print("Sorted  Array : ");
         for(int i=0; i<array.length;i++)
         {
             System.out.print(array[i] + " ");
         }
     }
}

But, I am getting a wrong output when I execute this code.

Original  Array : 5 4 7 2 1 9 3 6 10 8 
Sorted  Array : 1 4 5 2 6 7 3 8 9 10 

Can anyone please explain what is wrong. I have implemented this code exactly as given in "Introduction to algorithms" book. Thank you.

Answer 1

If you want some reference on how to implement quick sort, you could try checking the actual source code for Arrays.sort(*) in the jdk, which is a modified version of quick sort. (http://www.oracle.com/technetwork/java/javase/downloads/index.html to download if you don't already have src.zip in your jdk installation).

Answer 2

No you have not copied it directly :) I have it here...

for(int j=p; j<r-1; j++)

should be

for(int j=p; j<r; j++)

or

for(int j=p; j <= r-1; j++)

The book writes:

for j = p to r - 1

which includes r - 1. And remember the book has arrays which is starting from 1 and not 0. So generally the algorithms in the book should be "copied" with great care or with arrays which goes from 1.

Edit: Info about the algorithm for a comment The algorithm in the book takes the last element as pivot. It will therefore make it a terrible algorithm for already sorted arrays. It will end up in O(n^2) so no one should use this algorithm in production (unless you know what you are doing and what your input is) as arrays tend to be somewhat sorted. Java's build-in algorithm is more clever and you can read about it in the Javadoc