0

I am trying to write code for bucket sort, but am confused in bucket size of each bucket. My code is below. input array: {12, 11, 13, 5, 6, 7,10,22,4,16,1,26};

I am passing bucket size of each bucket >3 then I dont get the output in sorted order. It gives perfect ans for bucket size 1 and 2

public void bucsort(int[] arr,int bucketSize){

        if(arr.length==0) return;

        int max=arr[0];
        int min=arr[0];

        for(int i=0; i<arr.length;i++){
            if(arr[i]<min)
            {
                min=arr[i];
            }
            else
                max=arr[i];
        }
        int bucketCount= (max - min) / bucketSize + 1;
         List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketCount);
        // int divider= (max+1)/bucketCount;

         for (int i = 0; i < bucketCount; i++) {
                buckets.add(new ArrayList<Integer>());
            }
         for (int i = 0; i < arr.length; i++) {

                buckets.get((arr[i]-min) / bucketSize).add(arr[i]);
            }
         int currentIndex = 0;
            for (int i = 0; i < buckets.size(); i++) {
                Integer[] bucketArray = new Integer[buckets.get(i).size()];
                bucketArray = buckets.get(i).toArray(bucketArray);
                InsertionSort(bucketArray);
                for (int j = 0; j < bucketArray.length; j++) {
                    arr[currentIndex++] = bucketArray[j];
                }
            }       
    }

Is there any relation between no. of buckets and its size ?

I edited my method for max-min function and also debugged the program. There seems to be some mistake in my insertion sort

the code is:

public void InsertionSort(Integer[] arr){


        for(int i=1; i<arr.length; i++){
            int value=arr[i];
            int hole=i;

            while(hole>0 && arr[hole-1]>value){

                arr[hole]=arr[hole-1];

                hole--;
            }

            arr[hole-1]=value;
        }
    }

main func

public static void main(String[] args) {

        int arr[] = {12, 11, 13, 5, 6, 7,10,22,4,16,1,26};

        BucketSort ob = new BucketSort();
        ob.bucsort(arr, 5);
        printArray(arr);
    }
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

My output for bucket size 5 : 5 1 4 6 7 10 12 11 13 16 22 26 for size 3: 1 5 4 6 7 12 10 11 13 16 22 26 for size 2: 1 4 5 6 7 10 12 11 13 16 22 26

Improve this question
3
  • 1
    Hint: learn to use a debugger and/or how to use trace statements within your code in order to observe what it is doing. You got your code in front of you; so the only thing required to understand what it is doing ... is some curiosity on your end (I am telling you that because one learns programming from hunting down bugs; not by delegating that task to other people). And of course, when you go to ask ask; include all relevant code, not just half of it! Commented Dec 27, 2016 at 14:14
  • 1
    Could there be a bug in your InsertionSort method? We can help you better if you post complete code and complete output with different bucket sizes in your question (say, size 2 and size 4). Commented Dec 27, 2016 at 14:14
  • It’s an aside, I believe your way of finding the max happens to work for your input example, but will fail for other inputs. Commented Dec 27, 2016 at 14:15

2 Answers 2

Reset to default
1

Finding max-min is wrong...(you have some logical error)

int minValue = array[0];
        int maxValue = array[0];
        for (int i = 1; i < array.Length; i++) {
            if (array[i] < minValue) {
                minValue = array[i];
            } else if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }

On your code:

     1 4 3 
min  1 1 1
max  1 4 3

This will be the correct implemenation

for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j - 1];
                  arr[j - 1] = tmp;
                  j--;
            }
}

I will debug your code when I get time..

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

What you write is correct, but it is hardly an answer to the question.
@OleV.V.: There is no otherway we or anybody can comment on his/her implemenation. He/she should post the Insertion sort code also and with insertion sort correctly written this code works.
@coderredoc: I made the changes you told and debugged the program. There seems mistake in my insertion sort but I am not able to find what as my logic seems to be correct
@Ankita.: lemme check
Its working now.I was not replacing the final hole element with the value. thank you for pointing out my max function mistake
0

In your InsertionSort method you do

        int value=arr[i];
        int hole=i;

        while(hole>0 && arr[hole]>value){

At this point arr[hole] will always equal value, so you never get into the while loop. So nothing gets sorted. For small bucket sizes, you may be lucky that it doesn’t matter. For bucket size 1, it certainly doesn’t. Even for bucket size 2 you have a single error in the sorting. I get:

1 4 5 6 7 10 12 11 13 16 22 26

12 comes before 11 because those two numbers end up in the same bucket and don’t get sorted.

I took this from your comment: while (hole > 0 && arr[hole - 1] > value) {. On your request, now the method looks like this:

public void insertionSort(Integer[] arr) { // renamed to small i since it’s a method

    for (int i = 1; i < arr.length; i++) {
        int value = arr[i];
        int hole = i;

        while (hole > 0 && arr[hole - 1] > value) {

            arr[hole] = arr[hole - 1];

            hole--;
        }

        arr[hole] = value;
    }
}

Now I get correct sorting with all bucket sizes from 1 to 19. If you still have a problem, there must be something we are not doing the same way.

It’s an aside, but as has been mentioned a couple of times, there is a bug in your code for finding max. I tried this input:

    int arr[] = { 3, 10, 4 };

I get a maxof 4 (expected: 10) and then a java.lang.IndexOutOfBoundsException: Index: 1, Size: 1 at this line:

            buckets.get((arr[i]-min) / bucketSize).add(arr[i]);
Improve this answer

5 Comments

I have used while(hole>0 && arr[hole-1]>value)
Sounds like an improvement. Does it solve your problem?
I even tried using hole-i-1 and made changes accordingly in other parts of code...but it also does not work
I have edited the max function already in my IDE..just not edited it in my main question..I am getting 1 4 6 6 7 10 11 11 13 16 22 26 when I use hole=i-1.Can you please post your whole insertion sort code.It will be a great help
ok I got it.I was replacing arr[hole] = value; as arr[hole-1]=value so it was not getting sorted .Now its working properly. Thank you so much :)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.