Breaking
Sorting

# Bucket sort

Bucket sorting is a sorting algorithm that works with partitioning an array into a number of packets. Each bucket sorted individually using the same or different algorithm. Bucket sort and radix sort look like same. But it has some difference.

The following table shows the difference between Bucket sort and radix sort.

Write a program to implement bucket sort algorithm.

## source Code

```package com.dsacode.Algorithm.sorting;

import java.util.Arrays;

public class Bucketsort {

public static int[] bucketSort(int[] arr) {
int i, j;
int[] count = new int[arr.length];
Arrays.fill(count, 0);

for (i = 0; i < arr.length; i++) {
count[arr[i]]++;
}

for (i = 0, j = 0; i < count.length; i++) {
for (; count[i]>0; (count[i])--) {
arr[j++] = i;
}
}
return arr;
}

public static void main(String[] args) {

int[] arr = new int[] { 1, 3, 4, 6, 4, 2, 9, 1, 2, 9 };

System.out.println("unsorted array before sorting : " + Arrays.toString(arr));

arr = bucketSort(arr);

System.out.println("Sorted array After bucketSort sorting : " + Arrays.toString(arr));
}
}```

## Output

```Unsorted array before sorting: [1, 3, 4, 6, 4, 2, 9, 1, 2, 9]
Sorted array after bucket Sort sorting: [1, 1, 2, 2, 3, 4, 4, 6, 9, 9]```