File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes General Computing and the fly likes Algorithms: In Bucket-Sort when n=10 ... where/how calculate that goes to Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Engineering » General Computing
Bookmark "Algorithms: In Bucket-Sort when n=10 ... where/how calculate that goes to " Watch "Algorithms: In Bucket-Sort when n=10 ... where/how calculate that goes to " New topic
Author

Algorithms: In Bucket-Sort when n=10 ... where/how calculate that goes to

Leonidas Savvides
Ranch Hand

Joined: Jan 31, 2010
Posts: 403
In Bucket-Sort when n=10 , A=<0.11,0.21,0.31,...,0.71> 1-n , B=Array of Linked Lists 0-(n-1)

In statement
start
for i=1 to n
do insert A[i] into List B[|_nA[i]_|]
.........................
.........................
.........................
well if we have A[3]=0.31 where/how calculate that goes to B[] linked list

3x0.31=0.93 after where inserted?
Mike Peters
Ranch Hand

Joined: Oct 10, 2009
Posts: 67

If you have N numbers to sort where each number has a value between 0 and 1, then you create a list of N buckets. Define a range for each bucket, for example bucket(n) holds all elements with a value between n / N and (n + 1) / N. Then start traversing through your source values. Then value v is simply added to bucket FLOOR(v * N).

After all values have been put in a bucket, sort each bucket independently (for example with bucket sort, but you also apply another sorting algorithm. When all buckets have been sorted concatenate all buckets and you have the sorted result. Instead of sorting the buckets afterwards you may also keep the buckets sorted when placing a value in a bucket, for example with insertion sort.

Your example:

N = 10, A = {0.61, 0.21, 0.11, 0.44, 0.51, 0.41, 0.59, 0.62, 0.71, 0.31}

Define the following buckets:
Bucket 0 (value 0 - 0.1)
Bucket 1 (value 0.1 - 0.2)
Bucket 2 (value 0.2 - 0.3)
Bucket 3 (value 0.3 - 0.4)
Bucket 4 (value 0.4 - 0.5)
Bucket 5 (value 0.5 - 0.6)
Bucket 6 (value 0.6 - 0.7)
Bucket 7 (value 0.7 - 0.8)
Bucket 8 (value 0.8 - 0.9)
Bucket 9 (value 0.9 - 1.0)

Travers through A and put each value in its corresponding bucket, 0.61 in bucket 6, 0.21 in bucket 2, 0.11 in bucket 1, 0.44 in bucket 4, 0.51 in bucket 5, 0.41 in bucket 4, 0.59 in bucket 5, 0.62 in bucket 6, 0.71 in bucket 7, 0.31 in bucket 3:

Bucket 0: empty
Bucket 1: {0.11} has one element: finished
Bucket 2: {0.21} has one element: finished
Bucket 3: {0.31} has one element: finished
Bucket 4: {0.44, 0.41} NEEDS RESORTING -> {0.41, 0.44}
Bucket 5: {0.51, 0.59} is sorted: finished
Bucket 6: {0.61, 0.62} is sorted: finished
Bucket 7: {0.71} has one element: finished
Bucket 8: empty
Bucket 9: empty

Then resort bucket 4.

Finally concatenate all buckets in the result: {0.11, 0.21, 0.31, 0.41, 0.44, 0.51, 0.59, 0.61, 0.62, 0.71}

Ready!


Mike Peters
Leonidas Savvides
Ranch Hand

Joined: Jan 31, 2010
Posts: 403
IS THIS THAT YOU REFER AND MY TEXTBGOOK REFERS:




well if we have A[3]=0.31 where/how calculate that goes to B[] linked list

3x0.31=0.93 after where inserted?
Mike Peters
Ranch Hand

Joined: Oct 10, 2009
Posts: 67

Your book says:


where n = 10, A[3] = 0.31 so 10 * 0.31 = 3.1 -> so use B[3]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Algorithms: In Bucket-Sort when n=10 ... where/how calculate that goes to