Computer Science Canada :: View topic - How to Bucket Sort in Turing?

Computer Science Canada

How to Bucket Sort in Turing?

Author:

turingmachine [ Sat Nov 26, 2011 10:36 am ]

Post subject:

How to Bucket Sort in Turing?

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 Sad

. 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>

Author:

Aange10 [ Sat Nov 26, 2011 12:26 pm ]

Post subject:

RE:How to Bucket Sort in Turing?

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

Author:

Raknarg [ Sat Nov 26, 2011 1:54 pm ]

Post subject:

RE:How to Bucket Sort in Turing?

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.

Author:

Tony [ Sat Nov 26, 2011 2:03 pm ]

Post subject:

RE:How to Bucket Sort in Turing?

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

Author:

Aange10 [ Sat Nov 26, 2011 2:08 pm ]

Post subject:

Re: RE:How to Bucket Sort in Turing?

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?

Author:

Tony [ Sat Nov 26, 2011 2:13 pm ]

Post subject:

RE:How to Bucket Sort in Turing?

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.

Author:

Aange10 [ Sat Nov 26, 2011 2:25 pm ]

Post subject:

RE:How to Bucket Sort in Turing?

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.

Author:	Tony [ Sat Nov 26, 2011 2:39 pm ]
Post subject:	RE:How to Bucket Sort in Turing?
reading time -- ceil

Author:	Aange10 [ Sat Nov 26, 2011 2:47 pm ]
Post subject:	RE:How to Bucket Sort in Turing?
Amazing! Didn't know ceil was a procedure. Very cool, thanks Tony!

Author:	turingmachine [ Sat Nov 26, 2011 2:52 pm ]
Post subject:	RE:How to Bucket Sort in Turing?
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

Author:	Aange10 [ Sat Nov 26, 2011 2:57 pm ]
Post subject:	RE:How to Bucket Sort in Turing?
Not a problem! Good luck

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy