// DDseven28.java  will become  HeapSort.java
//converted from BubbleSort.java
// This program sorts an array's values into
// ascending order
import java.awt.*;
import javax.swing.*;

public class BucketSort extends JApplet {
 
   public void init()
   {
      JTextArea outputArea = new JTextArea();
      Container c = getContentPane();
      c.add( outputArea );

      int a[] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
      
      String output = "Data items in original order\n";

      for ( int i = 0; i < a.length; i++ ) 
         output += "   " + a[ i ];
 

	
      
      bucketSort( a );
      output += "\n\nData items in ascending order\n";

      for ( int i = 0; i < a.length; i++ ) 
         output += "   " + a[ i ];

      outputArea.setText( output );
   }


   // sort the elements of an array with bucket sort
   public void bucketSort( int a[] )
   {   
     
    int b[][] = new int[10] [a.length];

// find MAXINT the number of digits in the largest member of array a
int largest, MAXINT;
final int NINIT = -99;
largest = a[0];
for (int k=0 ;k < a.length ; k++){ 
 if (a[k] > largest ) largest = a[k];
} // end of k loop  


// MAXINT = 3;  // for this data

MAXINT = (  largest + "" ).length() ;
// distribution pass based on value on pass ( units place =pass 1)
for ( int pass = 1; pass < (MAXINT + 1) ; pass++ ) { // passes

// initialize b[][] to have value NINIT
for (int i=0;i<10;i++) { 
for (int j=0;j<b[i].length;j++){

b[i][j] = NINIT;
}//end of j loop
}//end ofi loop
//distributing 

for (int j=0; j < 10 ;j++ ){ 
int row = nDigit(a[j],pass );
for (int i=0;i < b[row].length ; i++){
if ( b[nDigit(a[j],pass)][i] == NINIT ){
           b[row][i]= a[j]; 
           break;  } 
}//end of i loop
}  //end of j loop

// gathering
 
int count=0; // start counting outside all loops
for( int j=0;j < 10; j++){
  for( int i=0;i < b[j].length;i++){
   if( b[j][i] != NINIT ){
    a[count] = b[j][i];
     count = count + 1;}
} // end loop over i
} // end loop over j


                       
}// end pass loop
} // end bucketSort method







public int onesDigit( int num) { // return the digit in ones place

return num - (num/10)*10;
}


public int nDigit(int num,int n){
 //returns digit n numbered from right( ones digit is n = 1)
if (n == 1) return onesDigit(num );
else{
    for (int k=1; k < n ; k++ ){
     num= num/10;
     num=onesDigit(num);}
  return num;}
}
}