Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Created by MOHIT on 01-10-2017.
- */
- import java.util.ArrayList;
- import java.util.Scanner;
- import static java.lang.Math.pow;
- import static java.util.Collections.max;
- // program to implement Bucket sort algorithm in c++
- public class bucket_sort {
- static Scanner sc = new Scanner(System.in);
- public static void main(String arg[]){
- ArrayList<Integer> sortedList;
- int length, element;
- ArrayList<Integer> myList = new ArrayList<Integer>();
- System.out.println("Program to implement counting sort algorithm in Java");
- System.out.print("Enter the number of Elements to be sorted : ");
- length = sc.nextInt();
- System.out.println("Enter the elements to be sorted : ");
- for(int index = 0; index < length; index++){
- element = sc.nextInt();
- myList.add(element);
- }
- System.out.println("\nThe list of elements before sorting is : ");
- displayList(myList);
- sortedList = bucket_sort(myList, length);
- System.out.println("\nThe sorted list is : ");
- displayList(sortedList);
- }
- // function to display the list of elements
- static void displayList(ArrayList<Integer> elementList){
- for(int index = 0; index < elementList.size(); index++) {
- System.out.print(elementList.get(index) + " ");
- }
- }
- // function to print all the bucket contents
- static void displayBuckets(ArrayList< ArrayList<Integer> > Buckets){
- ArrayList<Integer> temp;
- for(int index = 0; index<10; index++){
- if(Buckets.get(index).size() > 0) {
- System.out.println("Bucket " + index + " : ");
- displayList(Buckets.get(index));
- System.out.print("\n");
- }
- }
- }
- // function to merge the buckets into a vector
- static ArrayList <Integer> joinBuckets(ArrayList< ArrayList<Integer> > Buckets){
- ArrayList<Integer> temp;
- ArrayList<Integer> myList = new ArrayList<Integer>();
- for(int index = 0; index<10; index++){
- temp = Buckets.get(index);
- for(int index2 = 0; index2 < temp.size(); index2++){
- myList.add(temp.get(index2));
- }
- }
- return myList;
- }
- // method that sorts the list
- static ArrayList<Integer> bucket_sort(ArrayList<Integer> myList, int length){
- // finding the max element
- int maxElement = max(myList);
- int divisor = 10;
- int d = divisor;
- int element, rem, pos;
- ArrayList < ArrayList<Integer> > Buckets;
- ArrayList <Integer> temp;
- // couting the number of digits in the max element
- int digits = 0;
- while (maxElement != 0){
- maxElement = maxElement / 10;
- digits += 1;
- }
- Buckets = new ArrayList< ArrayList<Integer> >();
- // loop while divisor does not become 0
- while (divisor < pow(d,digits+1)){
- // initializing Buckets as 10 empty list
- for(int index = 0; index<10; index++){
- temp = new ArrayList<Integer>();
- Buckets.add(temp);
- }
- // iterating over the list
- for(int index = 0; index < length; index++){
- element = myList.get(index);
- // finding the bucket where the element need to be inserted
- rem = element % divisor;
- pos = rem / (divisor/10);
- // print(element, divisor, rem, pos)
- Buckets.get(pos).add(element);
- }
- System.out.println("\nAfter dividing by " + divisor + " the buckets are : ");
- displayBuckets(Buckets);
- // divide divisor by 10
- divisor = divisor * 10;
- myList.clear();
- myList = joinBuckets(Buckets);
- Buckets.clear();
- }
- return myList;
- }
- }
Add Comment
Please, Sign In to add comment