Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

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

Leonidas Savvides
Ranch Hand
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
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.

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}

Leonidas Savvides
Ranch Hand
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
Posts: 67