QSort with Random Partition

Question

The following implementation of qsort is from the book "Foundations of Algorithms" and therefore is believed to be correct. Below is my implementation in Java. It does not work. The problem is that when the partition is chosen at random, the generated partition is not correct. I am hoping that somebody can tell me what I am doing wrong:

Bob

import java.util.*;
public class qsort {
    public static void main(String []args)
    {
        int []a1 = { 1, 2, 3, -4, -5, 6, 7 };
        sort( 0, a1.length-1, a1 );
        printarray (a1 );

    }
static void sort( int low, int high, int []a )
{
    if ( low < high ) {
        int p = part( low, high, a);
        System.out.println( " p = " + p );
        printarray( a, low, p );
        System.out.println();
        sort( low, p-1, a);
        printarray( a, p, high );
        System.out.println();
        sort( p+1, high, a);
    }
}
static int part(int low, int high, int [] S) {
        int i;
        int j;
        int randspot;
        int pivotitem;
        int pivotpoint;
        Random random = new Random(456);
        randspot = random.nextInt(high-low +1)+low;
        pivotitem = S[randspot];
        j = low;
        for (i = low + 1; i <= high; i++)
            if (S[i] < pivotitem){
                j++;
                int temp = S[j];
                S[j] = S[i]; //exchanges S[i] and S[j]
                S[i] = temp;
            }
        pivotpoint = j;
        int temp = S[low];
        S[low] = S[pivotpoint];
        S[pivotpoint] = temp;
        return pivotpoint;
    }

static void printarray (int [] Test){
    for (int i = 0; i<Test.length; i++){
        if (i !=0 && i%10==0)
            System.out.println();
        System.out.print(Test[i]+ "\t");

    }
}
static void printarray (int [] Test, int low, int high){
    for (int i = low; i<high; i++)
        System.out.print(Test[i]+ "\t");
    }
}

Answer 1

You need to swap the pivot element with the low index element firstly and then do other operations. Check the code I added in the following code block.

static int part(int low, int high, int [] S) {
    int i;
    int j;
    int randspot;
    int pivotitem;
    int pivotpoint;
    Random random = new Random(456);
    randspot = random.nextInt(high-low +1)+low;
    System.out.println( " p = " + randspot );
    System.out.println( " value = " + S[randspot] );
    pivotitem = S[randspot];
    //---------------Start code block
    int temp1 = S[randspot];
    S[randspot] = S[low];
    S[low] = temp1;
    //---------------End code block
    j = low;
    for (i = low + 1; i <= high; i++)
        if (S[i] < pivotitem){
            j++;
            int temp = S[j];
            S[j] = S[i]; //exchanges S[i] and S[j]
            S[i] = temp;
        }
    pivotpoint = j;
    int temp = S[low];
    S[low] = S[pivotpoint];
    S[pivotpoint] = temp;
    return pivotpoint;
}