Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
Leonidas Savvides
Ranch Hand
Posts: 403
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 67
Debian Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
Leonidas Savvides
Ranch Hand
Posts: 403
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 67
Debian Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your book says:


where n = 10, A[3] = 0.31 so 10 * 0.31 = 3.1 -> so use B[3]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic