Question

In Java,

Bucket sort is a sorting algorithm that has O(n) performance on average.

I want you to write a function to perform bucket sort on a list of strings.

I also want you to test your function to see if it really work in linear time on average.

This code will need to be tested.

Finally, I want you to compare the performance of your function with Javasort method for lists.

Answer 1

import java.util.*;

class Main{

public static void bucketSort(ArrayList<String> words)

{

int maxlength=0;

for(int i=0;i<words.size();i++)

{

words.set(i,words.get(i).toUpperCase());

if(maxlength<words.get(i).length())

maxlength = words.get(i).length();

}

for(int j=maxlength-1;j>=0;j--)

{

Vector<Vector<String>> map = new Vector<Vector<String>>();

for(int i=0;i<27;i++)

{

map.add(null);

}

for(int i=0;i<words.size();i++)//Add words of of length j or greater to map(which is bucket here)

{

if(words.get(i).length()>j)

{

int val = (int)words.get(i).charAt(j) -65;

if(map.get(val)!= null)

{

map.get(val).add(words.get(i));

}

else

{

Vector<String> vecot = new Vector<String>();

vecot.add(words.get(i));

map.add(val, vecot);

}

}

else///Add words of of length<j to bucket 0

{

if(map.get(0) != null)

{

map.get(0).add(words.get(i));

}

else

{

Vector<String> vecot = new Vector<String>();

vecot.add(words.get(i));

map.add(0, vecot);

}

}

}

int count =0;

for(int i=0;i<map.size();i++)

{

if(map.get(i)!=null)

{

for(int k=0;k<map.get(i).size();k++)

{

words.set(count,map.get(i).get(k));

count++;

}

}

}

}

System.out.println("Next set :");

for(int i=0;i<words.size();i++)

{

System.out.println(words.get(i));

}

}

public static void main(String args[]){

long startTime = System.nanoTime();

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

ArrayList<String> a=new ArrayList<String>();

for(int i=0;i<n;i++){

a.add(sc.next());

}

bucketSort(a);

long stopTime = System.nanoTime();

System.out.println("Time taken: "+(stopTime - startTime));

}

}

The time taken by above function is of the order of n, i.e., O(n). The time taken by Java sort method for lists is O(n*log(n)).