Leonidas Savvides

Ranch Hand

Posts: 403

posted 7 years ago

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

.........................

.........................

.........................

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

3x0.31=0.93

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?**
posted 7 years ago

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!

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

Posts: 403