Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity

«
»
This is a java program to sort an elements in order n time. Bucket sort can be used to achieve this goal. Bucket sort is O(n) algorithm in time but takes more space, than the normal algorithms.

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

Output:

advertisement
$ javac Order_n_Sorting_Algorithm.java
$ java Order_n_Sorting_Algorithm
 
Sorting of randomly generated numbers using O(n) BUCKET SORT algorithm
 
Original Sequence: 
43 50 28 1 80 8 77 92 55 44 15 42 47 98 44 12 78 36 73 57 86 36 11 35 51 
Sorted Sequence: 
1 8 11 12 15 28 35 36 36 42 43 44 44 47 50 51 55 57 73 77 78 80 86 92 98

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.