import java.util.*;
public class BucketSorter
{
public static void main(String[] args)
{
new BucketSorter();
}
int size = inputInt("How many numbers do you want?");
int[] nums = new int[size];
int[][] bucket = new int[10][size];
int[] sorted = new int[size];
public BucketSorter()
{
makeRandom(100,900);
showArray(nums);
long started = new Date().getTime();
bucketSort();
long finished = new Date().getTime();
System.out.println("milliseconds = " + (finished - started));
if (checkSorted(sorted)==true)
{ System.out.println("List is sorted"); }
else
{ System.out.println("not sorted"); }
for (int b = 0; b < 10; b++)
{
System.out.println("== bucket " + b + "==");
showArray(bucket[b]);
}
System.out.println("==========");
System.out.println();
showArray(sorted);
}
public void showArray(int[] nums)
{
int max = findLast(nums) + 1;
if (max <= 9)
{ for (int x = 0; x <max; x++)
{ System.out.print(nums[x]+" "); }
System.out.println();
}
else
{ showSample(nums,max); }
}
public void showSample(int[] nums,int max)
{
System.out.println(nums[0] +
" " + nums[1] +
" " + nums[2] +
" .. " + nums[max/2-1] +
" " + nums[max/2] +
" " + nums[max/2 + 1] +
" .. " + nums[max-3] +
" " + nums[max-2] +
" " + nums[max-1]
);
}
public void makeRandom(int min, int max)
{ // fill nums[] array with random numbers
for (int x=0; x<size; x++)
{
nums[x] = (int)Math.floor(Math.random()*max + min);
}
}
public void bucketSort()
{
distribute();
for (int b=0; b <= 9; b++)
{ bubbleSort(bucket[b]); }
copyToSorted();
}
public void distribute()
{
for (int p = 0; p < size; p++)
{
if (nums[p] <100)
{ copyNumber( bucket[0] , nums[p]); }
else if (nums[p] < 200)
{ copyNumber( bucket[1] , nums[p]); }
else if (nums[p] < 300)
{ copyNumber( bucket[2] , nums[p]); }
else if (nums[p] < 400)
{ copyNumber( bucket[3] , nums[p]); }
else if (nums[p] < 500)
{ copyNumber( bucket[4] , nums[p]); }
else if (nums[p] < 600)
{ copyNumber( bucket[5] , nums[p]); }
else if (nums[p] < 700)
{ copyNumber( bucket[6] , nums[p]); }
else if (nums[p] < 800)
{ copyNumber( bucket[7] , nums[p]); }
else if (nums[p] < 900)
{ copyNumber( bucket[8] , nums[p]); }
else
{ copyNumber( bucket[9] , nums[p]); }
}
}
public void copyToSorted()
{
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[0][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[1][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[2][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[3][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[4][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[5][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[6][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[7][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[8][x]); }
for (int x = 0; x < size; x++)
{ copyNumber(sorted, bucket[9][x]); }
}
public void copyNumber(int[] buck , int n)
{ if (n>0)
{
int x = 0;
while (buck[x] > 0)
{ x = x + 1; }
buck[x] = n;
}
}
public boolean checkSorted(int[] nums)
{
boolean okay = true;
for (int x = 0; x < size-1 ; x = x + 1)
{
if (nums[x] > nums[x+1])
{ okay = false; }
}
return okay;
}
public int findLast(int[] nums)
{
int p = 0;
while (p < nums.length && nums[p] > 0 )
{
p = p + 1;
}
return p-1;
}
public void bubbleSort(int[] nums)
{
int last = findLast(nums);
for (int pass = 0; pass < last; pass++)
{ for (int x = 0; x < last; x++)
{
if (nums[x] > nums[x+1])
{
int temp = nums[x];
nums[x] = nums[x+1];
nums[x+1] = temp;
}
}
}
}
//==== IB Input Commands ==========================
static String input(String prompt)
{ String inputLine = "";
System.out.print(prompt);
try
{inputLine = (new java.io.BufferedReader(
new java.io.InputStreamReader(System.in))).readLine();
}
catch (Exception e)
{ String err = e.toString();
System.out.println(err);
inputLine = "";
}
return inputLine;
}
static int inputInt(String prompt)
{ int result=0;
try{result=Integer.valueOf(
input(prompt).trim()).intValue();}
catch (Exception e){result = 0;}
return result;
}
}
/*************************************************************************
The program executes a Bucket Sort - it seems to work correctly.
(1) The program ran for various sized lists and had times as shown below:
Size of List Milliseconds
10000 250
20000 1011
40000 3976
80000 18857
160000
(a) State whether the EFFICIENCY of the program appears to be:
Approximately O(n^2) , much better than O(n^2),
or much worse than O(n^2).
(b) Sketch a graph of list SIZE vs MILLISECONDS.
(c) Predict the approximate amount of time required to sort 160,000 items.
(d) Predict the approximate amount of time to sort 800,000 items.
(2) Rewrite the CopyToSorted method to use a loop rather than
copying similar commands 10 times.
(3) Explain the purpose of the FindLast method.
(4) Explain the purpose of the CopyNumber method.
Decide whether this method is efficient or inefficient.
(5) Without changing the program, describe a MORE EFFICIENT ALGORITHM
for the CopyNumber method.
(6) Change MakeRandom(100,900) to MakeRandom(10,90).
Make a table like #1 above and study the speed of the program now.
Is it faster, slower, or about the same? Explain WHY this happens.
(7) If 100 buckets were used instead of 10, would the sorting
method run faster, slower, or about the same? Explain why.
**************************************************************************/