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.
http://www.growingwiththeweb.com/2015/06/bucket-sort.html
Usage
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
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:
还有的方法是维护一个size为k的最大堆
Read full article from 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);
- 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
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-sortUsage
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 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.
}
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:
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