Newsgroup: it.comp.java
Titolo: Implementazione algoritmo bucketsort

Ho provato a implementare l'algoritmo bucketsort, per numeri di 2
cifre in questo caso, per l'ordinamento degli array.
L'algoritmo funziona a metà. Alcuni elementi degli array mi vengono
duplicati altri mi vengono cancellati, però quelli che vengono
stampati sono messi in ordine, che bella consolazione!
Come posso risolvere?
Grazie
void bucketsort(int a[], int size){
 const int siz= size-1;
 int bucket[10][siz];
 int cifre[2];
 int prima, seconda;
 for (int h=0; h<2; h++){
 
  for(int o=0; o<10; o++)
  for (int t=0; t<siz; t++)
   bucket[o][t]=100;
 
 for(int u=0; u<size; u++){
  cifre[1]=a[u]/10;
  cifre[0]=a[u]%10;
  bucket[cifre[h]][u]=a[u];
 }
 for(int k=0; k<10; k++){
  for(int g=0; g<siz; g++)
   if(bucket[k][g]!=100)
    a[k]=bucket[k][g];
 }
 }
}

 ha scritto nel messaggio
news:d24d832e.03111...@posting.google.com...

/*
 * Copyright Derek Park 2001
 * All rights reserved
 */
import java.util.NoSuchElementException;
/**
 *BucketSort provides a quick, memory intensive sort for int arrays
 */
public class BucketSort {
   /**
    *Sorts an int array passed by client
    */
   public static void bucketSort(int [] inputArray) {
      /*
       *instantiate BucketSets to use for sorting
       */
      BucketSet currentBucketSet = new BucketSet(inputArray.length);
      BucketSet prevBucketSet = new BucketSet(inputArray.length);
      BucketSet tempBucketSet;
      // stores the current digit to sort (ie: 1, 10, 100, 1000, etc.)
      int currentDigit = 1;
      // loop until through array
      for (int i = 0; i < inputArray.length; i++) {
         // use Bucket's add method to
         currentBucketSet.add((inputArray[i] / currentDigit) % 10,
                             inputArray[i], currentDigit);
      }
      // Add from one BucketSet to the next until sorted
      while (currentBucketSet.notSorted()) {
         // set prev to current and vice versa
         tempBucketSet = prevBucketSet;
         prevBucketSet = currentBucketSet;
         currentBucketSet = tempBucketSet;
         currentBucketSet.setNotSorted(false);  // reset the BucketSet
         currentDigit *= 10;  // move digit to next power
         while (!(prevBucketSet.isEmpty())) {
            // get next element from previous BucketSet
            int element = prevBucketSet.getNext();
            // add element to the current BucketSet
            currentBucketSet.add((element / currentDigit) % 10,
                                element, currentDigit);
         }
      }
      // copy from last BucketSet used to the original array
      for (int i = 0; i < inputArray.length; i++) {
         inputArray[i] = currentBucketSet.getNext();
      }
   }
   /* BucketSet is a supporting class for BucketSort,
    * used to hold Buckets
    */
   private static class BucketSet {
      int [][] bucket;                       // array to hold Buckets
      int [] bucketDepth = {-1,-1,-1,-1,-1,
                            -1,-1,-1,-1,-1}; // depth of each bucket
      int totalInBuckets = 0;                // total number in all buckets
      boolean notSorted = false;
      public BucketSet(int inputCols) {
         bucket = new int [10][inputCols];   // create buckets based on
input
      }
      public boolean notSorted() {
         return notSorted;
      }
      public void setNotSorted(boolean inputNotSorted){  // reset Bucket
         notSorted = inputNotSorted;
      }
      public boolean isEmpty() {
         return (totalInBuckets == 0);
      }
      /*
       * Adds to one bucket in the BucketSet
       * place is the bucket (0 - 9) to store the value in
       * inputValue is the value to be stored
       * currentDigit is the power to opertate on (1, 10, 100)
       */
      public void add(int place, int inputValue, int currentDigit) {
         bucketDepth[place]++;
         bucket[place][bucketDepth[place]] = inputValue;  // add to bucket
         totalInBuckets++;
         if (inputValue > currentDigit) { // if further sorting is needed
            notSorted = true;             // set variables accordingly
         }
      }
      // Returns a value from a bucket, starting with the zero bucket
      public int getNext() {
         for (int i = 0; i < 10; i++) { // loop until non-empty bucket
found
            if (bucketDepth[i] >= 0 ) { // if current bucket is not empty
               int returnValue = bucket[i][0]; // save the element to be
returned
               //take from the top of the bucket and move the rest up
               for (int j = 1; j <= bucketDepth[i]; j++){
                  bucket[i][j - 1] = bucket[i][j];
               }
               bucketDepth[i]--;          // bucket has one less
               totalInBuckets--;          // total has one less
               return returnValue;        // return the one saved as temp
            }
         }
         /*
          * This won't be reached unless the user failed to check isEmpty()
          * Hopefully the user will at least catch the exception
          */
         throw new NoSuchElementException("Element below zero");
      }
   }
}