How to Bucket Sort in Turing?

[turingmachine]

What is it you are trying to achieve?
<I'm supposed to bucket sort in Turing but I'm having difficulty. The program should allow to user the enter in the amount of numbers they want to sort and then randomize that many numbers. These numbers should then be sorted using Bucket Sort. >


What is the problem you are having?
<From what I understand, in bucket sort, you take the list to be sorted and you put them in different buckets. Numbers between a certain number range of say 1-10 go in bucket, numbers in the range of 11-20 go in another bucket, etc. I can't figure out how to create arrays for each new bucket required because I don't know how many number ranges there will be when the program randomizes the numbers. Also, my bubble sort algorithm isn't working and I think in Bucket Sort, you put the list of numbers into different buckets and then bubble sort within each bucket? I'm really stuck . I've made an array to store the variables being randomized but I don't know where to go from there. >


Describe what you have tried to solve this problem
I can't think of anything, I've throughly searched the net for any solutions, and I finally just came here.


Post any relevant code (You may choose to attach the file instead of posting the code if it is too long)
<Here's what I have so far, no luck though :/ >

Turing:

var n : int var temp : int put "How many numbers would you like to be sorted?" get n var bucket : array 1 .. n of int for i : 1 .. n     randint (bucket (i), 1, 100)     put bucket (i) end for for i : 1 .. n - 1     for j : 1 .. n - 1         if bucket (i + 1) < bucket (i)         then             temp := bucket(i)             bucket(i) := bucket(i+1)             bucket(i+1) := temp         end if     end for end for put "" for i : 1 .. n     put bucket (i) end for put "The time elapsed was " , Time.Elapsed/1000," seconds"

Edit : Here's the new version, I fixed the bubble sort, but it's still not bucket sort :/. I still need to find out how to put everything in each bucket, then I can bubble sort, and then I need to find out how to put it all back together in the end.

Turing:

var n : int var temp : int put "How many numbers would you like to be sorted?" get n var bucket : array 1 .. n of int for i : 1 .. n     randint (bucket (i), 1, 100)     put bucket (i) end for for i : 1 .. n - 1     for j : 1 .. n - 1         if bucket (j) > bucket (j + 1)                 then             temp := bucket (j)             bucket (j) := bucket (j + 1)             bucket (j + 1) := temp         end if     end for end for put "" for i : 1 .. n     put bucket (i) end for put "The time elapsed was ", Time.Elapsed / 1000, " seconds"

Edit : I think I've assigned each number range to each bucket but I'm not sure how to apply bubble sort to each one and how to merge them together at the end.

Turing:

put "Now bucket sort will sort those numbers" for i : 1 .. n     if bucket (i) < 10             then         bucket1 (i) := bucket (i)     elsif bucket (i) < 20 and bucket (i) > 9             then         bucket2 (i) := bucket (i)     elsif bucket (i) < 30 and bucket (i) > 19             then         bucket3 (i) := bucket (i)     elsif bucket (i) < 40 and bucket (i) > 29             then         bucket4 (i) := bucket (i)     elsif bucket (i) < 50 and bucket (i) > 39             then         bucket5 (i) := bucket (i)     elsif bucket (i) < 60 and bucket (i) > 49             then         bucket6 (i) := bucket (i)     elsif bucket (i) < 70 and bucket (i) > 59             then         bucket7 (i) := bucket (i)     elsif bucket (i) < 80 and bucket (i) > 69             then         bucket8 (i) := bucket (i)     elsif bucket (i) < 90 and bucket (i) > 79             then         bucket9 (i) := bucket (i)     elsif bucket (i) < 101 and bucket (i) > 89             then         bucket10 (i) := bucket (i)     end if end for

Please specify what version of Turing you are using
<4.1.1>

[Aange10]

http://en.wikipedia.org/wiki/Bucket_sort

Has lots of information, a step by step list, and pseudo code of how to do this.

Quote:

I can't figure out how to create arrays for each new bucket required because I don't know how many number ranges there will be when the program randomizes the number

But you do know how many number ranges there are. There are n number ranges.

So lets make that into buckets

Turing:

% ________ How many  buckets we will have ________ % If n is divisble by 10, we cane have an *exact* amount of buckets if n mod 10 = 0 then     new buckets, (n div 10) % Otherwise we need an extra bucket else     has_extra := true     new buckets, ((n div 10) + 1) end if

Now to organize our buckets, we will just have a few for loops, and an initialization.

Turing:

View.Set ("text") % ________ Get the Input _________ var n : int := 101 % User inputted var number : array 1 .. n of int var has_extra : boolean := false % Flag to tell us if we have an extra bucket var buckets : flexible array 1 .. 0 of string % ________ How many  buckets we will have ________ % If n is divisble by 10, we can have an *exact* amount of buckets if n mod 10 = 0 then     new buckets, (n div 10) % Otherwise we need an extra bucket else     has_extra := true     new buckets, ((n div 10) + 1) end if % _________ Intialize ________ for i : 1 .. upper (number)     % Random number between 1 and whatever n is     number (i) := Rand.Int (1, n) end for for i : 1 .. upper (buckets)     buckets (i) := "" end for % ________ Organize the Bucket (by 10s) ________ % Go through by 10s for j : 10 .. upper (number) + 10 by 10     if has_extra = false and j = upper (number) + 10 then         % This will not do the last bucket, if we don't have an extra     else         % Go through the array         for i : 1 .. upper (number)             if number (i) > (j - 10) and number (i) <= j then                 % We are using a string so we don't add our numbers, and we                 % use | so we can tell the numbers apart                 buckets ((j div 10)) += intstr (number (i)) + "|"             end if         end for     end if end for % _________ Show the buckets __________ for i : 1 .. upper (buckets)     put "Bucket " + intstr (i) + ": " + buckets (i) end for

The for loops are the only really tricky parts. As for organizing, I'd look up bubble organizing on wikipedia. My friend taught be this a little while back, so I'll share with you what he gave me to learn bubble sorting. It's attached at the bottom

[Raknarg]

The key to this problem is using flexible arrays. A flexible array is the same as a regular array, but you can resize the upper bound. You resize like this:

Turing:

var arr : flexible array 1 .. 5 of int new arr, 6

That'll change the upper bound to 6. You can use this for unknown array bounds.

[Tony]

instead of

code:

else ... ((n div 10) + 1)

you could have

code:

ceil(n / 10)

which will generalize the two cases. Unless you need to do something special with has_extra, but edge cases are typically discouraged.

code:

elsif bucket (i) < 90 and bucket (i) > 79             then         bucket9 (i) := bucket (i)

This doesn't work for any case above 100 elements, and works poorly for cases less than 100. Remember that index can be evaluated at runtime

code:

my_array(herp mod derp) := some_value

[Aange10]

Tony @ 26/11/2011, 1:03 pm wrote:

instead of

code:

else ... ((n div 10) + 1)

you could have

code:

ceil(n / 10)

which will generalize the two cases. Unless you need to do something special with has_extra, but edge cases are typically discouraged.

Wouldn't n/10 (lets say n = 101) wouldn't that then give me 10.1. Which you can't have an array defined as 1 .. 10.1?

The extra bucket really wouldn't be 'extra' at all. It's just easier naming conventions


Edit: And what is an edge case?

[Tony]

code:

ceil(10.1) == 11

edit: edge case is a type of input that is treated in a special way, somehow different from general input. E.g., having "has_extra" flag for some but not all inputs. This introduces extra code paths and complexity.

[Aange10]

Im not sure what == is >..<.

But

Turing:

var foo : array 1 .. (101/10) of int

is a syntax error.

As for a special case, I try to keep it as irrelevant as i can; I try to keep it as similar to everything else, so there is less variety in what is happening.

[Tony]

reading time -- ceil

[Aange10]

Amazing! Didn't know ceil was a procedure. Very cool, thanks Tony!

[turingmachine]

Thanks guys, especially Aange10, that code w/ documentation helped clear it up a lot ! Now I think I know how to out bubble sort each bucket and then put them together at the end .. thanks

[Aange10]

Not a problem! Good luck