QuickSort partition algorithm

Question

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.

Lasse Espeholt · Accepted Answer · 2010-08-09 21:54:16Z

14

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

edited Aug 9, 2010 at 21:54

answered Aug 9, 2010 at 21:40

Lasse Espeholt

17.8k5 gold badges65 silver badges102 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Race Over a year ago

Thanks for the answer lasseespheholt. My book contains the pseudocode as for j = p to r-1. That was the only problem.

Merlyn Morgan-Graham Over a year ago

@Race: en.wikipedia.org/wiki/Quicksort has a very similar algorithm, though it seems that pivotIndex and left, as described in that article, are combined in your/the textbook's algorithm.

Lasse Espeholt Over a year ago

@Merlyn see edit :) It uses the rightmost element and therefore does not need a additional pivot index.

Rich Over a year ago

Another thing to note with this implementation are the input bounds. For example, as highlighted in the answer, due to the pivot selection nearly sorted data preforms badly. So if you ask this implementation to sort 1,000,000 between numbers 0 <= 50, you will encounter a stack overflow (something which doesn't show up on a small dataset).

whaley · Accepted Answer · 2010-08-09 21:40:03Z

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

answered Aug 9, 2010 at 21:40

whaley

16.3k10 gold badges60 silver badges68 bronze badges

Comments

mdev · Accepted Answer · 2013-08-18 19:15:44Z

Providing one more implementation in java. It is also based on the same algorithm and takes care of duplicate elements in the array too.

    public void sort( int[] inputArray, int lo, int high){
          int pivotIndex = partition(inputArray,lo,high);
         System. out .println("Got PivotIndex as " + pivotIndex);
          if (lo < pivotIndex -1)
                sort(inputArray,lo,pivotIndex - 1);
          if (pivotIndex+1 < high)
                sort(inputArray,pivotIndex+1,high);
          return ;
    }

    private int partition( int[] inputArray, int leftPtr,int rightPtr)
   {
         printArray(inputArray);
          int pivot = inputArray[leftPtr];
          while (leftPtr<rightPtr){
                 while (inputArray[leftPtr]<pivot)
                       leftPtr++;
                 while (inputArray[rightPtr]>pivot)
                       rightPtr--;
                 if (leftPtr<rightPtr)
                {
                       exchange(inputArray,leftPtr,rightPtr);

                          //Cases which have repeated numbers...
                        if (inputArray[leftPtr] == inputArray[rightPtr])
                             leftPtr++;
                }
         }
          return leftPtr;//return any one
   }

Collectives™ on Stack Overflow

QuickSort partition algorithm

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related