BucketSoRt

[Danii]

As an example, consider the following array of 9 integers in the range 1 to 5:

[2, 3, 2, 1, 4, 5, 2, 3, 1]

The count array would contain the following values:

[2, 3, 2, 1, 1]

Working from this set of counts, the sorted array would be:

[1, 1, 2, 2, 2, 3, 3, 4, 5]

Bucket sort has the unfortunate property of destroying (and recreating) the original data set, which is why it can only be used for integer values. However, it is very fast when you only need to sort integers.

Write a small Java program that does the following:

1. Prompts the user to enter a positive integer n. Your program will sort a list of integers in the range 1-n.
2. Randomly generates a list of 100 integers in the specified range (Use the Random class to do this -- an example will be provided shortly on Blackboard).
3. Prints the unsorted list to the screen.
4. Uses bucket sort to sort the data set. Write a separate bucketSort() method to do the sorting and return a sorted version of the data set; don't do the sorting directly in main()!
5. Prints the sorted data set to the screen.

import java.util.Arrays;
import java.util.Scanner;

public class Bucketsort {

  public static int[] bucketSort(int[] arr) {
    int i, j;
    int[] count = new int[arr.length];
    Arrays.fill(count, 0);

    for(i = 0; i < arr.length; i++ ) {
      count[arr[i]]++;
    }

    for(i=0,j=0; i < count.length; i++) {
      for(; count[i]>0; (count[i])--) {
        arr[j++] = i;
      }
    }

    return arr;
  }


  public static void main(String[] args) {

	//System.out.println(" Input an integer ");
	 //Scanner sc = new Scanner(System.in);
	//Random r = new Random();
   
    int[] arr = new int[] {2, 3, 2, 1, 4, 5, 2, 3, 1};
  
    for(int i = 0; i < arr.length; i++ ) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();


    arr = bucketSort(arr);

    for(int i = 0; i < arr.length; i++ ) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();

  }
}

//output: 112223345

I had a few problem writing this code so instead I wrote it with the given example in it
I know that I have to use System.out.println("enter a integer ") ...an Scanner... and random class but I cant seem to put all these together I think theres something wrong with the counter. HElp

thanks.

[PoovenM]

Well it seems to me that you're a bit unfamiliar with Java. Here's a few hints in using the classes:

The Scanner object you created: Scanner sc = new Scanner(System.in); is perfectly correct. Next you have to ask object to get data from the console (since you specified System.in as you input stream). This is achieved using the .nextInt() method. You'll find there are a whole range of 'next' methods than can be called - as listed in the API (Java Documentation). int value = sc.nextInt() Since you want to store the read values in an array of course at some point you'll read in data in a loop - similiar to displaying the contents of an array.

If you want to use a random number generator, perhaps use the one that comes with Math class: double a = Math.random(); This will generate numbers in the range of 0 to 1 (not inclusive of 1). If we multiply this number by say 15 then we get numbers in the range 0 to 15 (not inclusive of 15). If we add 5 to this number we get numbers in the range 5 to 30 (not inclusive of 30): double a = Math.random()*15 + 5; So how would you generate numbers in a range? It's actually quite logical ;) Btw you'd have to type cast to get an integer value: int randNum = (int)(Math.random()*15 + 5); So basically the (int) forces whatever is infront of it to become an int.

If you want more help, you'll need to give some concrete questions... just so that we know you're thinking.