Has GeekViewpoint been there for you? Will you be there for us?
We need beta users for our mobile app Prefies.
To help us, please go to prefies.com and use access code “GeekViewpoint”.
Many thanks and Happy Holidays!

Bucket Sort
by Isai Damier

/*****************************************************************************
 * Author: Isai Damier
 * Title: Bucketsort
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a disordered list of integers, rearrange them in natural order.
 *
 * Sample Input: {8,5,3,1,9,6,0,7,4,2,5}
 * Sample Output: {0,1,2,3,4,5,6,7,8,9,5}
 *
 * Time Complexity of Solution:
 *     Best Case O(n); Average Case O(n); Worst Case O(n).
 *
 * Approach:
 *   If it sounds too good to be true, then most likely it's not true.
 *   Bucketsort is not an exception to this adage. For bucketsort to work at
 *   its blazing efficiency, there are multiple prerequisites. First the
 *   hash function that is used to partition the elements need to be very
 *   good and must produce ordered hash: if i < k then hash(i) < hash(k).
 *   Second, the elements to be sorted must be uniformly distributed.
 *
 *   The aforementioned aside, bucket sort is actually very good considering
 *   that counting sort is reasonably speaking its upper bound. And counting
 *   sort is very fast. The particular distinction for bucket sort is that
 *   it uses a hash function to partition the keys of the input array, so
 *   that multiple keys may hash to the same bucket. Hence each bucket must
 *   effectively be a growable list; similar to radix sort.
 *
 *   Numerous Internet sites, including university pages, have erroneously
 *   written counting sort code and call them bucket sort. Bucket sort uses
 *   a hash function to distribute keys; counting sort creates a bucket for
 *   each key. Indeed there are perhaps greater similarities between radix
 *   sort and bucket sort, than there are between counting sort and bucket sort.
 *
 *   In the presented program Java's Collections.sort(C) is used to sort each
 *   bucket. This is to inculcate that the bucket sort algorithm does not
 *   specify which sorting technique to use on the buckets. A programmer may
 *   choose to continuously use bucket sort on each bucket until the
 *   collection is sorted (in the manner of the radix sort program below).
 *   Whichever sorting method is used on the buckets, bucket sort still
 *   tends toward O(n).
 *
 ****************************************************************************/ 
 public void bucketsort(int[] input) {
  //get hash codes
  final int[] code = hash(input);
  //create and initialize buckets to ArrayList: O(n)
  List<Integer>[] buckets = new List[code[1]];
  for (int i = 0; i < code[1]; i++) {
    buckets[i] = new ArrayList<Integer>();
  }
  //distribute data into buckets: O(n)
  for (int i : input) {
    buckets[hash(i, code)].add(i);
  }
  /**
   * Sort each bucket: O(n).
   * I mentioned above that the worst case for bucket sort is counting
   * sort. That's because in the worst case, bucket sort may end up
   * with one bucket per key. In such case, sorting each bucket would
   * take 1^2 = O(1). Even after allowing for some probabilistic
   * variance, to sort each bucket would still take 2-1/n, which is
   * still a constant. Hence, sorting all the buckets takes O(n).
   ***/
  for (List bucket : buckets) {
    Collections.sort(bucket);
  }
  int ndx = 0;
  //merge the buckets: O(n)
  for (int b = 0; b < buckets.length; b++) {
    for (int v : buckets[b]) {
      input[ndx++] = v;
    }
  }
}

private int[] hash(int[] input) {
  int m = input[0];
  for (int i = 1; i < input.length; i++) {
    if (m < input[i]) {
      m = input[i];
    }
  }
  return new int[]{m, (int) Math.sqrt(input.length)};
}

private int hash(int i, int[] code) {
  return (int) ((double) i / code[0] * (code[1] - 1));
}
import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {
  
  @Test
  public void testBucketsort() {
    System.out.println(""bucketsort"");
    int[] A = {8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5};
    Sorting instance = new Sorting();
    instance.bucketsort(A);
    for (int i = 1; i < A.length; i++) {
      if (A[i - 1] > A[i]) {
        fail(""bucketsort method fails."");
      }
    }
  }
}
Phuzz! Turn your photo into a puzzle!