**Bucket sort, or bin sort,**is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

**Steps:**

1. Set up an array
of initially empty "buckets".

2.

**Scatter:**Go over the original array, putting each object in its bucket.
3. Sort each
non-empty bucket.

4.

**Gather:**Visit the buckets in order and put all elements back into the original array.

**Elements are distributed among bins**

**Elements are sorted within each bin**

Bucket sort assumes that the input is drawn from a

**uniform distribution**and has an average-case running time of O(n). The computational complexity estimates involve the number of buckets.

**Worst case performance:**O(n^2)

**Best case performance:**Omega(n+k)

**Average case performance:**Theta(n+k)

**Worst case space complexity:**O(n.k)

**Simple implementation of Bucket sort**

import java.util.*;

public class BucketSort {

**public**

**static**

**void**

**sort(**

**int**

**[]**

**tmpData**

**,**

**int**

**maxVal**

**) {**

**/****

*** Initialize the Buckets Array to store elements**

****/**

**int**

**[]**

**bucket**

**=**

**new**

**int**

**[**

**maxVal**

**+1];**

**for**

**(**

**int**

**i**

**=0;**

**i**

**<**

**bucket**

**.**

**length**

**;**

**i**

**++) {**

**bucket**

**[**

**i**

**]=0;**

**}**

**/****

*** Element as index and**

*** value stored at array index is occurence.**

****/**

**for**

**(**

**int**

**i**

**=0;**

**i**

**<**

**tmpData**

**.**

**length**

**;**

**i**

**++) {**

**bucket**

**[**

**tmpData**

**[**

**i**

**]]++;**

**}**

**/****

*** Restore all the elements in sorted order.**

****/**

**int**

**outPos**

**=0;**

**for**

**(**

**int**

**i**

**=0;**

**i**

**<**

**bucket**

**.**

**length**

**;**

**i**

**++) {**

**for**

**(**

**int**

**j**

**=0;**

**j**

**<**

**bucket**

**[**

**i**

**];**

**j**

**++) {**

**tmpData**

**[**

**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("Array:" + Arrays.*toString*(data));*sort*(data,maxVal);

System.

*out*.println("Sorted Array:" + Arrays.*toString*(data));
}

}

**Output:**

Array: [5, 3, 0, 2, 4, 1, 0, 5, 2, 3, 1, 4]

Sorted Array:
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]

## No comments:

## Post a Comment