m2skills

Bucket sort java

Oct 13th, 2017
23
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.97 KB | None | 0 0
  1. /**
  2.  * Created by MOHIT on 01-10-2017.
  3.  */
  4. import java.util.ArrayList;
  5. import java.util.Scanner;
  6.  
  7. import static java.lang.Math.pow;
  8. import static java.util.Collections.max;
  9.  
  10. // program to implement Bucket sort algorithm in c++
  11. public class bucket_sort {
  12.     static Scanner sc = new Scanner(System.in);
  13.     public static void main(String arg[]){
  14.  
  15.         ArrayList<Integer> sortedList;
  16.         int length, element;
  17.  
  18.         ArrayList<Integer> myList = new ArrayList<Integer>();
  19.         System.out.println("Program to implement counting sort algorithm in Java");
  20.         System.out.print("Enter the number of Elements to be sorted : ");
  21.         length = sc.nextInt();
  22.  
  23.         System.out.println("Enter the elements to be sorted : ");
  24.         for(int index = 0; index < length; index++){
  25.             element = sc.nextInt();
  26.             myList.add(element);
  27.         }
  28.  
  29.         System.out.println("\nThe list of elements before sorting is : ");
  30.         displayList(myList);
  31.  
  32.         sortedList = bucket_sort(myList, length);
  33.  
  34.         System.out.println("\nThe sorted list is : ");
  35.         displayList(sortedList);
  36.     }
  37.  
  38.     // function to display the list of elements
  39.     static void displayList(ArrayList<Integer> elementList){
  40.         for(int index = 0; index < elementList.size(); index++) {
  41.             System.out.print(elementList.get(index) + " ");
  42.         }
  43.     }
  44.  
  45.     // function to print all the bucket contents
  46.     static void displayBuckets(ArrayList< ArrayList<Integer> > Buckets){
  47.         ArrayList<Integer> temp;
  48.         for(int index = 0; index<10; index++){
  49.             if(Buckets.get(index).size() > 0) {
  50.                 System.out.println("Bucket " + index + " : ");
  51.                 displayList(Buckets.get(index));
  52.                 System.out.print("\n");
  53.             }
  54.         }
  55.     }
  56.  
  57.     // function to merge the buckets into a vector
  58.     static ArrayList <Integer> joinBuckets(ArrayList< ArrayList<Integer> > Buckets){
  59.         ArrayList<Integer> temp;
  60.         ArrayList<Integer> myList = new ArrayList<Integer>();
  61.  
  62.         for(int index = 0; index<10; index++){
  63.             temp = Buckets.get(index);
  64.             for(int index2 = 0; index2 < temp.size(); index2++){
  65.                 myList.add(temp.get(index2));
  66.             }
  67.         }
  68.         return myList;
  69.     }
  70.  
  71.     // method that sorts the list
  72.     static ArrayList<Integer> bucket_sort(ArrayList<Integer> myList, int length){
  73.  
  74.         // finding the max element
  75.         int maxElement = max(myList);
  76.         int divisor = 10;
  77.         int d = divisor;
  78.         int element, rem, pos;
  79.         ArrayList < ArrayList<Integer> > Buckets;
  80.         ArrayList <Integer> temp;
  81.         // couting the number of digits in the max element
  82.         int digits = 0;
  83.         while (maxElement != 0){
  84.             maxElement = maxElement / 10;
  85.             digits += 1;
  86.         }
  87.  
  88.         Buckets = new ArrayList< ArrayList<Integer> >();
  89.  
  90.  
  91.         // loop while divisor does not become 0
  92.         while (divisor < pow(d,digits+1)){
  93.             // initializing Buckets as 10 empty list
  94.             for(int index = 0; index<10; index++){
  95.                 temp = new ArrayList<Integer>();
  96.                 Buckets.add(temp);
  97.             }
  98.  
  99.             // iterating over the list
  100.             for(int index = 0; index < length; index++){
  101.                 element = myList.get(index);
  102.                 // finding the bucket where the element need to be inserted
  103.                 rem = element % divisor;
  104.                 pos = rem / (divisor/10);
  105.  
  106.                 // print(element, divisor, rem, pos)
  107.                 Buckets.get(pos).add(element);
  108.             }
  109.  
  110.             System.out.println("\nAfter dividing by " + divisor + " the buckets are : ");
  111.             displayBuckets(Buckets);
  112.  
  113.             // divide divisor by 10
  114.             divisor = divisor * 10;
  115.  
  116.             myList.clear();
  117.             myList = joinBuckets(Buckets);
  118.  
  119.             Buckets.clear();
  120.         }
  121.         return myList;
  122.     }
  123. }
Add Comment
Please, Sign In to add comment