Java – quicksort partitioning algorithm

I'm trying to write a quick sort algorithm using the cormen algorithm textbook Here 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,q-1);
            qSort(a,q+1,r);
        }
     }

     private int Partition(int[] a,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,length-1);

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

However, when I execute this code, an error is output

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

Anyone can explain what's wrong I implemented this code completely according to the instructions in the book "Introduction to algorithm" thank you.

Solution

No, you didn't copy it directly:) I'm here

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

should

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

or

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

The book reads:

for j = p to r - 1

This includes R – 1 And remember that the array of this book starts with 1 instead of 0 So generally speaking, the algorithms in this book should be very careful to "copy" or arrays starting from 1

Editor: for information about the review algorithm, the algorithm in the book uses the last element as the pivot Therefore, for sorted arrays, it will become a terrible algorithm It will end with O (n ^ 2), so no one should use this algorithm in production (unless you know what you're doing and what your input is), because arrays often have some sort Java's built-in algorithm is smarter, and you can read it in Javadoc