Massive Algorithms: Bucket Sort

Bucket Sort

Bucket Sort | GeeksforGeeks
Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem.
Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range. How do we sort the numbers efficiently?

Counting sort can not be applied here as we use keys as index in counting sort. Here keys are floating point numbers.

Bucket sort it’s the perfect sorting algorithm for the sequence above. We must know in advance that the integers are fairly well distributed over an interval (i, j). Then we can divide this interval in N equal sub-intervals (or buckets). We’ll put each number in its corresponding bucket. Finally for every bucket that contains more than one number we’ll use some linear sorting algorithm.

bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.

The main step to analyze is step 3. This step also takes O(n) time on average if all numbers are uniformly distributed.

void bucketSort(float arr[], int n)

{

    // 1) Create n empty buckets

    vector<float> b[n];

    // 2) Put array elements in different buckets

    for (int i=0; i<n; i++)

{

       int bi = n*arr[i]; // Index in bucket

       b[bi].push_back(arr[i]);

}

    // 3) Sort individual buckets

    for (int i=0; i<n; i++)

       sort(b[i].begin(), b[i].end());

    // 4) Concatenate all buckets into arr[]

    int index = 0;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < b[i].size(); j++)

          arr[index++] = b[i][j];

}

float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};

int n = sizeof(arr)/sizeof(arr[0]);

bucketSort(arr, n);

http://www.growingwiththeweb.com/2015/06/bucket-sort.html

Counting sort: buckets hold only a single value
Bucket sort: buckets hold a range of values
Radix sort: buckets hold values based on digits within their values

The most common implementation of bucket sort works by splitting the array of size

n

into

k

buckets, each of which house a value range of

n/k

. The buckets are then sorted using a simple sorting algorithm that works well on the expected data, such as insertion sort.

public class BucketSort {
    private static final int DEFAULT_BUCKET_SIZE = 5;

    public static void sort(Integer[] array) {
        sort(array, DEFAULT_BUCKET_SIZE);
    }

    public static void sort(Integer[] array, int bucketSize) {
        if (array.length == 0) {
            return;
        }

        // Determine minimum and maximum values
        Integer minValue = array[0];
        Integer maxValue = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < minValue) {
                minValue = array[i];
            } else if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }

        // Initialise buckets
        int bucketCount = (maxValue - minValue) / bucketSize + 1;
        List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<Integer>());
        }

        // Distribute input array values into buckets
        for (int i = 0; i < array.length; i++) {
            buckets.get((array[i] - minValue) / bucketSize).add(array[i]);
        }

        // Sort buckets and place back into input array
        int currentIndex = 0;
        for (int i = 0; i < buckets.size(); i++) {
            Integer[] bucketArray = new Integer[buckets.get(i).size()];
            bucketArray = buckets.get(i).toArray(bucketArray);
            InsertionSort.sort(bucketArray);
            for (int j = 0; j < bucketArray.length; j++) {
                array[currentIndex++] = bucketArray[j];
            }
        }
    }
}

http://en.algoritmy.net/article/41160/Bucket-sort
Usage

Bucket sort can be used for distributed sorting – each bucket can be ordered by a different thread or even by a different computer. Another use case is a sorting of huge input data, which cannot be loaded into the main memory by an ordinary $O(n\cdot \log(n))$ algorithm. This problem can be solved by dividing the data into sufficiently small buckets, sorting them one by one by appropriate algorithm, while storing rest of the data in the external memory (e.g. hard drive).

public static int[] bucketSort(int[] array, int bucketCount) {

08.if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");

09.if (array.length <= 1) return array; //trivially sorted

10.

11.int high = array[0];

12.int low = array[0];

13.for (int i = 1; i < array.length; i++) { //find the range of input elements

14.if (array[i] > high) high = array[i];

15.if (array[i] < low) low = array[i];

16.}

17.double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket

18.

19.ArrayList<Integer> buckets[] = new ArrayList[bucketCount];

20.for (int i = 0; i < bucketCount; i++) { //initialize buckets

21.buckets[i] = new ArrayList();

22.}

23.

24.for (int i = 0; i < array.length; i++) { //partition the input array

25.buckets[(int)((array[i] - low)/interval)].add(array[i]);

26.}

27.

28.int pointer = 0;

29.for (int i = 0; i < buckets.length; i++) {

30.Collections.sort(buckets[i]); //mergeSort

31.for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets

32.array[pointer] = buckets[i].get(j);

33.pointer++;

34.}

35.}

36.return array;

37.}

https://www-927.ibm.com/ibm/cas/hspc/student/algorithms/BucketSort.html
Problem 2. Museum

At a nature museum, you are in charge of the ancient rock collection. Your scientists have collected a number of shiny, coloured rocks, and have compiled the information into a text file. Each rock is listed like this: rock_weight, rock_colour, so for example, {23, blue}.As head of the rock collection, you need to write a program that will sort these rocks into separate weight categories (0-10 grams, 11-20 grams, 21-30 grams, 31-40 grams and 41+ grams) using bucket sort. Then, you must use bucket sort again to separate the weight-categorized rocks into colour order, so red is first, then orange, yellow, green, blue, purple and grey.
http://www.cs.hmc.edu/~keller/courses/cs60/s98/examples/Sort/bucketsort.java
Also refer to http://java.dzone.com/articles/algorithm-week-bucket-sort
http://en.wikipedia.org/wiki/Bucket_sort

http://www.geeksforgeeks.org/bucket-sort-to-sort-an-array-with-negative-numbers/
Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the problem of sorting a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range

How to modify Bucket Sort to sort both positive and negative numbers?
Example:

Input : arr[] = { -0.897, 0.565, 0.656, -0.1234, 0, 0.3434 } 
Output : -0.897 -0.1234  0 0.3434 0.565 0.656

sortMixed(arr[], n)
1) Split array into two parts 
   create two Empty vector Neg[], Pos[] 
   (for negative and positive element respectively)
   Store all negative element in Neg[] by converting
   into positive (Neg[i] = -1 * Arr[i] )
   Store all +ve in pos[]  (pos[i] =  Arr[i])
2) Call function bucketSortPositive(Pos, pos.size())
   Call function bucketSortPositive(Neg, Neg.size())

bucketSortPositive(arr[], n)
3) Create n empty buckets (Or lists).
4) Do following for every array element arr[i]. 
       a) Insert arr[i] into bucket[n*array[i]]
5) Sort individual buckets using insertion sort.
6) Concatenate all sorted buckets.

void bucketSort(vector<float> &arr, int n)

{

    // 1) Create n empty buckets

    vector<float> b[n];

    // 2) Put array elements in different

    //    buckets

    for (int i=0; i<n; i++)

{

        int bi = n*arr[i]; // Index in bucket

        b[bi].push_back(arr[i]);

}

    // 3) Sort individual buckets

    for (int i=0; i<n; i++)

        sort(b[i].begin(), b[i].end());

    // 4) Concatenate all buckets into arr[]

    int index = 0;

    arr.clear();

    for (int i = 0; i < n; i++)

        for (int j = 0; j < b[i].size(); j++)

            arr.push_back(b[i][j]);

}

// This function mainly slpits array into two

// and then calls bucketSort() for two arrays.

void sortMixed(float arr[], int n)

{

    vector<float>Neg ;

    vector<float>Pos;

    // traverse array elements

    for (int i=0; i<n; i++)

{

        if (arr[i] < 0)

            // store -Ve elements by

            // converting into +ve element

            Neg.push_back (-1 * arr[i]) ;

        else

            // store +ve elements

            Pos.push_back (arr[i]) ;

}

    bucketSort(Neg, (int)Neg.size());

    bucketSort(Pos, (int)Pos.size());

    // First store elements of Neg[] array

    // by converting into -ve

    for (int i=0; i < Neg.size(); i++)

        arr[i] = -1 * Neg[ Neg.size() -1 - i];

    // store +ve element

    for(int j=Neg.size(); j < n; j++)

        arr[j] = Pos[j - Neg.size()];

}

http://www.cnblogs.com/EdwardLiu/p/6546969.html
Give n points on 2-D plane, find the K closest points to origin

Based on bucket sort:

16     public static List<Coordinate> findK(List<Coordinate> input, int k) {
17         HashMap<Coordinate, Integer> map = new HashMap<Coordinate, Integer>();
18         int longest = 0;
19         for (Coordinate each : input) {
20             int distance = cal(each);
21             map.put(each, distance);
22             longest = Math.max(longest, distance);
23         }
24         
25         List<Coordinate>[] arr = new ArrayList[longest + 1];
26         for (Coordinate each : map.keySet()) {
27             int dis = map.get(each);
28             if (arr[dis] == null)
29                 arr[dis] = new ArrayList<Coordinate>();
30             arr[dis].add(each);
31         }
32         
33         List<Coordinate> res = new ArrayList<Coordinate>();
34         for (int i=0; i<arr.length-1 && res.size()<k; i++) {
35             if (arr[i] != null)
36                 res.addAll(arr[i]);
37         }
38         return res;
39     }
40     
41     public static int cal(Coordinate a) {
42         return a.x * a.x + a.y * a.y;
43     }

还有的方法是维护一个size为k的最大堆

13     public List<Point> KClosest(List<Point> input, int k) {
14         List<Point> res = new LinkedList<Point>();
15         PriorityQueue<Point> pq = new PriorityQueue<Point>(10, new Comparator<Point>() {
16             public int compare(Point a, Point b) {
17                 return (b.x * b.x + b.y * b.y) - (a.x * a.x + a.y * a.y);
18             }            
19         });
20         
21         for (Point each : input) {
22             pq.offer(each);
23             if (pq.size() > k) pq.poll();
24         }
25         while (!pq.isEmpty()) {
26             res.add(0, pq.poll());
27         }
28         return res;
29     }

Read full article from Bucket Sort | GeeksforGeeks

Bucket Sort

Labels

Popular Posts