Java Program to Implement Bucket Sort

«
»
This is a java program to sort the numbers using the Bucket Sort Technique. The algorithm allocates the number of memory locations equal to maximum number and initializes all to zero, then each location is incremented as the numbers appears. The time complexity of the algorithm is O(n).

Here is the source code of the Java Program to Implement Bucket Sort. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to sort numbers using bucket sort
  2. import java.util.Random;
  3.  
  4. public class Bucket_Sort 
  5. {
  6.     static int[] sort(int[] sequence, int maxValue) 
  7.     {
  8.         // Bucket Sort
  9.         int[] Bucket = new int[maxValue + 1];
  10.         int[] sorted_sequence = new int[sequence.length];
  11.  
  12.         for (int i = 0; i < sequence.length; i++)
  13.             Bucket[sequence[i]]++;
  14.  
  15.         int outPos = 0;
  16.         for (int i = 0; i < Bucket.length; i++)
  17.             for (int j = 0; j < Bucket[i]; j++)
  18.                 sorted_sequence[outPos++] = i;
  19.  
  20.         return sorted_sequence;
  21.     }
  22.  
  23.     static void printSequence(int[] sorted_sequence) 
  24.     {
  25.         for (int i = 0; i < sorted_sequence.length; i++)
  26.             System.out.print(sorted_sequence[i] + " ");
  27.     }
  28.  
  29.     static int maxValue(int[] sequence) 
  30.     {
  31.         int maxValue = 0;
  32.         for (int i = 0; i < sequence.length; i++)
  33.             if (sequence[i] > maxValue)
  34.                 maxValue = sequence[i];
  35.         return maxValue;
  36.     }
  37.  
  38.     public static void main(String args[]) 
  39.     {
  40.         System.out
  41.                 .println("Sorting of randomly generated numbers using BUCKET SORT");
  42.         Random random = new Random();
  43.         int N = 20;
  44.         int[] sequence = new int[N];
  45.  
  46.         for (int i = 0; i < N; i++)
  47.             sequence[i] = Math.abs(random.nextInt(100));
  48.  
  49.         int maxValue = maxValue(sequence);
  50.  
  51.         System.out.println("\nOriginal Sequence: ");
  52.         printSequence(sequence);
  53.  
  54.         System.out.println("\nSorted Sequence: ");
  55.         printSequence(sort(sequence, maxValue));
  56.     }
  57. }

Output:

advertisement
$ javac Bucket_Sort.java
$ java Bucket_Sort
 
Sorting of randomly generated numbers using BUCKET SORT
 
Original Sequence: 
95 9 95 87 8 81 18 54 57 53 92 15 38 24 8 56 29 69 64 66 
Sorted Sequence: 
8 8 9 15 18 24 29 38 53 54 56 57 64 66 69 81 87 92 95 95

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Reference Books in Java Programming, Data Structures and Algorithms.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter