Search code examples
sortingindexingbucket

Bucket index in Bucket Sort

I'm trying to improve my bucket sort for large number over 10000.I'm not quite sure, why my code isn't performing well on large numbers. My Bucket Sort algorithm for array of size n:

  1. Create array of linked list of size n

  2. Calculate range for numbers

  3. Calculate interval for each bucket

  4. Calculate index for bucket, where to put particular number (Problem: I calculated index by constantly subtracting interval from number and increment counter,every time i subtract interval.Counter is the index) I believe this particular way of finding index takes very long for large numbers. How can i improve finding index of buckets?

P.S. i heard there's way to preprocess array and find min and max number of array. Then calculate index by subtracting particular number from min. index=number-min. I didn't quite get the idea of calculating index. Questions: 1. Is this efficient way to find index? 2. How do i handle cases when i have array of size 4, and numbers 31,34,51,56? 31 goes to bucket 0,34 goes to bucket 3, how about 51 and 56? 3. Is there any other way to calculate index?

Solution

  • You can find your index faster through Division. Index = value / interval. If the first interval starts at 'min' instead of 0, then use (value-min) as the numerator.