This week's book giveaway is in the Jobs Discussion forum. We're giving away four copies of Java Interview Guide and have Anthony DePalma on-line! See this thread for details.

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

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}

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

posted

0

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