Bucket Sort in Java

The sorting technique using which the elements of the given array is distributed into many numbers of buckets to sort each of the bucket by using different sorting algorithms or by using bucket sorting algorithm recursively is called bucket sort in Java whose space complexity is O(1), worst case complexity is O(n^2), best case complexity is Omega(n+k) and average case complexity is theta(n+k) and bucket sorting technique to sort the given elements of the array works at a faster speed when compared to other sorting algorithms and the elements of the array to be sorted using bucket sort algorithm must be uniformly distributed.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

The function to perform bucket sort in Java is as follows:

public static int[] bucketsort(int[] array, int maximum_value)
{
int[] newbucket = new int[maximum_value + 1];
int[] sorted_array = new int[array.length];
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}

where array is the input array to be sorted using bucket sort algorithm, maximum_value is the maximum_value present in the given array and sorted_array is the resultant array consisted of sorted elements.

Working of Bucket Sort Algorithm in Java

Working of Bucket sort algorithm in Java is as follows:

• The first step in Bucket sort algorithm is to create an empty array which is considered to be the buckets.
• The second step is to traverse the entire input array whose elements are to be sorted and add each element to the bucket.
• The third step is to sort each element in the buckets.
• The fourth step is to traverse all the elements in the buckets and add each one of them in sorted order to the original input array.

Examples of Bucket Sort in Java

Following are examples are given below:

Example #1

Java program to sort the elements of the given array by implementing bucket sort algorithm and then display the sorted elements of the array as the output on the screen:

 Code:

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

Output:

In the above program, we are creating an empty array called newbucket which is considered as bucket array. Then we are creating another empty array called sorted_array to store the result array. Then we are traversing through the input array to add each element to the bucket array. Then we are sorting each element in the bucket array and adding each sorted element in order to the original input array. Then we are defining a function to find the maximum value in the input array in order to sort the given array using bucket sort technique. Then the main function is called within which we display the resulting array. The output is shown in the snapshot above.

Example #2

Java program to sort the elements of the given array by implementing bucket sort algorithm and then display the sorted elements of the array as the output on the screen:

Code:

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={ 60, 80, 50, 90, 30, 70, 20 };
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

Output:

In the above program, we are creating an empty array called a new bucket which is considered a bucket array. Then we are creating another empty array called sorted_array to store the result array. Then we are traversing through the input array to add each element to the bucket array. Then we are sorting each element in the bucket array and adding each sorted element in order to the original input array. Then we are defining a function to find the maximum value in the input array in order to sort the given array using the bucket sort technique. Then the main function is called within which we display the resulting array. The output is shown in the snapshot above.

The above is the detailed content of Bucket Sort in Java. For more information, please follow other related articles on the PHP Chinese website!