Bucket Sort (alternatively know as bin sort) is an algorithm that sorts
numbers and comes under the category of distribution sort.
This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:
Thanks.
This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:
- Partition a given array into a number of buckets
- One-by-one the numbers in the array are placed in the designated bucket
- Now, only sort the bucket that bare numbers by recursively applying this Bucket Sorting algorithm
- Now, visiting the buckets in order, the numbers should be sorted
public class BucketSort{ public static void sort(int[] a, int maxVal) { int [] bucket=new int[maxVal+1]; for (int i=0; i<bucket.length; i++) { bucket[i]=0; } for (int i=0; i<a.length; i++) { bucket[a[i]]++; } int outPos=0; for (int i=0; i<bucket.length; i++) { for (int j=0; j<bucket[i]; j++) { a[outPos++]=i; } } } public static void main(String[] args) { int maxVal=5; int [] data= {5,3,0,2,4,1,0,5,2,3,1,4}; System.out.println("Before: " + Arrays.toString(data)); sort(data,maxVal); System.out.println("After: " + Arrays.toString(data)); } }
Thanks.
0 comments:
Post a Comment