tags:

views:

136

answers:

3

Hi, I want to implement the Binary Quicksort algorithm from [Robert Sedgewick's book][1]. It looks like this:

    public class quickb{
public static final int bitsword=32;

public static void quicksortB(int a[],int l,int r,int d){
 int i=l;
int j=r;
if (r<=l || d>bitsword) return ;

 while (j!=i)
{

  while (digit(a[i],d)==0 && (i<j)) i++;
while (digit(a[j],d)==1 && (j>i)) j--;
   int t=a[i];
a[i]=a[j];
a[j]=t;
}
      if (digit(a[r],d)== 0) j--;

  quicksortB(a,l,j-1,d+1);
 quicksortB(a,j,r,d+1);




}

public static void main(String[]args){
   int a[]=new int[]{4,7,3,9,8,2};


 quicksortB(a,0,a.length-1,0);

 for (int i=0;i<a.length;i++){
  System.out.println(a[i]);
}



}

 public static int digit(int m,int d){


    return (m>>d)&1;



}
}

i have changed it compiles but result is 4 8 9 3 7 2 maybe code is in correct in book can anybody help me to solve this problem?

A: 

Try this in your main function:

for (int i=0;i<a.length-1;i++){ 
  System.out.println(a[i]); 
} 
Brett
no no effect thanks
A: 

shouldn't

while (digit(a[j],d)==1 && (j>i)) j++;

be

while (digit(a[j],d)==1 && (j>i)) j--;

?

TJMonk15
You're right about the first one, but the second one is correct as it is ( with j++). This is just to check to see if all of the elements are have 0's as this digit, and in that case j will not have moved and the j needs to be incremented in order to sort the correct regions.
Justin Peel
Ah, ok thanks. Fixed.
TJMonk15
A: 

With TJMonk15 correction (-- in the while).
I've tried to execute and that's what happens

The final array is 489372, with this "log":

Swapping (from left to right): 7 with 8
Swapping (from left to right): 3 with 3
Swapping (from left to right): 3 with 9
Swapping (from left to right): 3 with 3
Swapping (from left to right): 7 with 7

No swapping is correct according to me..

I don't understand why int j=r-1 and you use length-1 as r, then j is equal to length-2 at the beginning.

Fabio F.
ok i have changed j=r but it does not work yet
i think code is incorrect in book because as other codes there is probability that this code is also incorrect