Write a class called Bag.java which will sort in ascending order an array arr[]

Question

Write a class called Bag.java which will sort in ascending order an array arr[] of double from 0 to 1, using the following algorithm.

Indicate in comment, the Time Complexity of your algorithm.

1. Create n bags , n being the number of element in the array.

2. For every element of the array , put this element in a bag so that arr[ i ] is inserted into bag number n*arr [i] + 1 .

3. Sort each bags individually using the Selection sort.

4. Put all those values back in the array arr[] so that the array is now sorted.

Example :

Assume the array arr : 0.15 0.25 0.5 0.18 0.014 0.2 We have 6 elements, therefore 6 bags, which are filled as followed The elements in Bag 1 are sorted , as well as the element in Bag 2. The new sorted array is : 0.014 0.15 0.18 0.2 0.25 0.5

Note : This algorithm is a variation of the Bucket sorting algorithm.

Explanation / Answer

Bag.java :
______

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Bag {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       System.out.println("Enter number of elements in array: ");
       int n = sc.nextInt();
       double arr[] = new double[n];
       Map<Integer,ArrayList<Double>> bag = new HashMap<Integer,ArrayList<Double>>();
       System.out.println("Enter array elements:");
       for(int i=0;i<n;i++)
           arr[i] = sc.nextDouble();
       for(int i=0;i<n;i++){
           int index = (int) (n*arr[i] + 1);
           if(bag.containsKey(index)){
               ArrayList<Double> al = bag.get(index);
               al.add(arr[i]);
               bag.put(index,al);
           }
           else{
               ArrayList<Double> al = new ArrayList<Double>();
               al.add(arr[i]);
               bag.put(index,al);
           }
       }
       int k = 0;
       for(int key : bag.keySet()){
           System.out.print(" Bag "+key+" elements: ");
           ArrayList<Double> values = bag.get(key);
           double a[] = new double[values.size()];
           for(int i=0;i<values.size();i++){
               a[i] = values.get(i);
               System.out.print(values.get(i)+" ");
           }
           int len = a.length;
           for(int i=0;i<len-1;i++){
               int pos = i;
               for(int j=i+1;j<len;j++){
                   if(a[j]<a[pos])
                       pos = j;
               }
               double temp = a[i];
               a[i] = a[pos];
               a[pos] = temp;
           }
           for(int i=0;i<a.length;i++){
               arr[k] = a[i];
               k++;
           }
       }
       System.out.println(" Sorted Array:");
       for(int i=0;i<arr.length;i++)
           System.out.print(arr[i]+" ");
   }
}

Sample Input and Output :
_____________________

Enter number of elements in array:
10
Enter array elements:
0.15 0.25 0.5 0.18 0.014 0.2 0.7 0.4 0.42 0.12

Bag 1 elements: 0.014
Bag 2 elements: 0.15 0.18 0.12
Bag 3 elements: 0.25 0.2
Bag 5 elements: 0.4 0.42
Bag 6 elements: 0.5
Bag 8 elements: 0.7

Sorted Array:
0.014 0.12 0.15 0.18 0.2 0.25 0.4 0.42 0.5 0.7

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.