Sorting in Turing and Returning Arrays from Function

andytyk · **Posted:** Mon Jul 19, 2004 11:40 pm

I was playing with different sorts in Turing, and list operations such as Merge Sort, Quick Sort etc. and needed to pass arrays in recursion to functions and return them as well.

I tried the obvious first and found out that Turing will not permit it. So after digging through the Reference manual and finding nothing that will help, I decided to write a class that simply consists of a flexible array and some basic array functions (add, count members, etc.) and had a flexible array of pointers. So the functions simply returned the index in which the pointer lay for the result.

This resulted in a horrendously low sorting speed. Using Quicksort and a pregenerated list of 1000 Rand.Real s. Sorting using the first term of the set as the pivot resulted in 288ms while using the average as the pivot resulted in 277ms. Is there a better way to handle this, or are there better ways to sort in Turing?

Dan · **Posted:** Tue Jul 20, 2004 11:02 am

While bubble sort may not be the fastested but it is easy and i know will work in turing for shure.

this is bubble sort in c++

code:

for (i=0; i<n-1; i++)
{
for (j=0; j<n-1-i; j++)
{
if (a[j+1] < a[j])
{
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}

Where a is the array and n is the number if elments in the array. The -i part in the 2nd for is not need but incereces the speed. a smiple verson in turing whould be:

code:

for i : 1 .. numOfElements
for ii : 2 .. numOfElements
if myArray(ii - 1) < myArray(ii) then
%switchs the values
var temp : int := myArray(ii - 1)
myArray(ii - 1) := myArray(ii)
myArray(ii) := temp
end if
end for
end for

andytyk · **Posted:** Tue Jul 20, 2004 12:18 pm

Hmm... I'm just thinking about the speed, sorting 100,000 Rand.Reals I can get around 3000-4000 sorts per second using Quicksort without a combo with Insertion.

This is the code I wrote:

code:

class arrays

export addterm, avg, quickavg, numterms, getterm

var core : flexible array 1 .. 0 of real

function getterm (termno : int) : real
result core (termno)
end getterm

function addterm (a : real) : boolean
new core, upper (core) + 1
core (upper (core)) := a
result true
end addterm

function avg : real
var sum : real := 0
for k : 1 .. upper (core)
sum := core (k) + sum
end for
result sum / upper (core)
end avg

function quickavg (a : int) : real
var sum : real := 0
for k : 1 .. a
sum := core (k) + sum
end for
result sum / a
end quickavg

function numterms : int
result upper (core)
end numterms

end arrays

var pseudoarray : flexible array 1 .. 0 of pointer to arrays
var dummy : boolean

function newarray : int
new pseudoarray, upper (pseudoarray) + 1
new pseudoarray (upper (pseudoarray))
result upper (pseudoarray)
end newarray

var test1, test2 : int

test1 := newarray
test2 := newarray

var size := 50000
var tempreal : real

for abc : 1 .. size
tempreal := Rand.Real
dummy := pseudoarray (test1) -> addterm (tempreal)
dummy := pseudoarray (test2) -> addterm (tempreal)
end for

function join (a : int, b : int) : int
var newtarget : int := newarray
for m : 1 .. pseudoarray (a) -> numterms
dummy := pseudoarray (newtarget) -> addterm (pseudoarray (a) -> getterm (m))
end for
for n : 1 .. pseudoarray (b) -> numterms
dummy := pseudoarray (newtarget) -> addterm (pseudoarray (b) -> getterm (n))
end for
free pseudoarray (a)
free pseudoarray (b)
result newtarget
end join

function merge (a : int, b : int) : int
var m, n : int := 1
var ai, bi : boolean
var newtarget : int := newarray
loop
if pseudoarray (a) -> getterm (m) >= pseudoarray (b) -> getterm (n) then
dummy := pseudoarray (newtarget) -> addterm (pseudoarray (b) -> getterm (n))
n := n + 1
else
dummy := pseudoarray (newtarget) -> addterm (pseudoarray (a) -> getterm (m))
m := m + 1
end if
ai := m - 1 = pseudoarray (a) -> numterms
bi := n - 1 = pseudoarray (b) -> numterms
exit when ai or bi
end loop
if not ai then
for k : 1 .. pseudoarray (a) -> numterms - (m)
dummy := pseudoarray (newtarget) -> addterm (pseudoarray (a) -> getterm (m + k))
end for
elsif not bi then
for k : 1 .. pseudoarray (b) -> numterms - (n)
dummy := pseudoarray (newtarget) -> addterm (pseudoarray (b) -> getterm (n + k))
end for
end if
free pseudoarray (a)
free pseudoarray (b)
result newtarget
end merge

function quicksort (a : int) : int
if pseudoarray (a) -> numterms <= 1 then
result a
else
var ara, arb, arc : int
var avg : real := pseudoarray (a) -> getterm (1)
ara := newarray
arb := newarray
arc := newarray
for k : 1 .. pseudoarray (a) -> numterms
if pseudoarray (a) -> getterm (k) < avg then
dummy := pseudoarray (ara) -> addterm (pseudoarray (a) -> getterm (k))
elsif pseudoarray (a) -> getterm (k) = avg then
dummy := pseudoarray (arb) -> addterm (pseudoarray (a) -> getterm (k))
else
dummy := pseudoarray (arc) -> addterm (pseudoarray (a) -> getterm (k))
end if
end for
free pseudoarray (a)
result join (join (quicksort (ara), arb), quicksort (arc))
end if
end quicksort

function quicksortb (a : int) : int
if pseudoarray (a) -> numterms <= 1 then
result a
else
var ara, arb, arc : int
var avg : real := pseudoarray (a) -> avg
ara := newarray
arb := newarray
arc := newarray
for k : 1 .. pseudoarray (a) -> numterms
if pseudoarray (a) -> getterm (k) < avg then
dummy := pseudoarray (ara) -> addterm (pseudoarray (a) -> getterm (k))
elsif pseudoarray (a) -> getterm (k) = avg then
dummy := pseudoarray (arb) -> addterm (pseudoarray (a) -> getterm (k))
else
dummy := pseudoarray (arc) -> addterm (pseudoarray (a) -> getterm (k))
end if
end for
free pseudoarray(a)
result join (join (quicksortb (ara), arb), quicksortb (arc))
end if
end quicksortb

var testabc : int := Time.Elapsed
var result1 := quicksort (test1)
put "Sorted using the first term as the dividing factor in Quicksort: ", round (1000 / (((Time.Elapsed - testabc) / size) / 2)), " sorts per second."

testabc := Time.Elapsed
var result2 := quicksortb (test2)
put "Sorted using the average as the dividing factor in Quicksort: ", round (1000 / (((Time.Elapsed - testabc) / size) / 2)), " sorts per second."

Since I'm a novice at this, I'm sure there are plenty of ways to speed up the code, or a better way to handle the arrays. Memory usage is also a problem. I left out a free statement in one of the quicksorts and ended up with a 2 gig pagefile usage when sorting 1 million Rand.Real s. Memory usage is down to around 200-300 MBs when sorting 1 million Rand.Reals.

Any suggestions or comments?

Tony · **Posted:** Tue Jul 20, 2004 1:44 pm

instead of making up an array class (known as vector in C++ and ArrayList in Java I belive), why not just stick to the basics?

rether then passing the entire array back and forth, can't you just declear it as global where every function can access it? I think your bottleneck is that you have to pass the entire array to the next function on each pass of the loop or whatever. This would slow down your program exponensially, and you always want to avoid that.

andytyk · **Posted:** Tue Jul 20, 2004 2:53 pm

Hmm... if we just declared the arrays as globals (which means there will be a predefined number of them), we'll be stuck with using in-place sorting algorithms then..

And Bubblesort is great for small arrays (such as those with less than 100 values), its speed matches the Quicksort (avg) at around 5000 sorts per second. But if we're going to be sorting larger arrays... Confused

Array Size - BubbleSort - Quicksort (using average pivot) (sorts per second)
--------------------------------------------------------------------
50 - 11000 - 6250
100 - 6250 - 5000
500 - 1114 - 4065
2500 - 226 - 3374
3000 - 185 -3398

I'll play around with it to see where the bottleneck is.

Dan · **Posted:** Tue Jul 20, 2004 4:16 pm

Just whondering, what are u making that u need to sort an array of 3000? or are you just trying to find the best posable method of sorting?

It realy is to bad turing dose not have lists or vectors like java and c++.

andytyk · **Posted:** Tue Jul 20, 2004 5:28 pm

Well, a little of both, I want to find the fastest sorting method in Turing as well as finding which triangles to draw first in my 3d engine by sorting the z-values.

Coming from C++, PHP, etc. getting Turing to do what you want is a pain.

Using a QuickBubble sort (Quick sort for initial breaking down of arrays to small arrays of 20 or less then bubble sorting) yields pretty good results, I think I'll do a QuickInsertion and then compare.

Array size -> QuickBubble (sorts per second)
50 - 12500
100 - 11111
1000 - 5952
10000 - 4492
100000 - 3364

Catalyst · **Posted:** Wed Jul 21, 2004 1:20 am

well if ur using it for a 3d engine then you can sometimes get away with a bubble if u do maybe ten passes (and the rest is fast) because of temporal coherence

Catalyst · **Posted:** Wed Jul 21, 2004 1:26 am

would this do for a quicksort for your needs? (my tests get 9k-10k sorts per second)

code:

procedure qSort (var a : array 1 .. * of real, var b : array 1 .. * of int, l, h : int)
if l < h then
var aH : real
var bH : int
var i : int := l
var j : int := h
var mid : real := a (l)
loop
loop
exit when a (i) >= mid
i += 1
end loop
loop
exit when a (j) <= mid
j -= 1
end loop
if i <= j then
aH := a (i)
a (i) := a (j)
a (j) := aH
bH := b (i)
b (i) := b (j)
b (j) := bH
i += 1
j -= 1
end if
exit when i > j
end loop
qSort (a, b, l, j)
qSort (a, b, i, h)
end if
end qSort

andytyk · **Posted:** Wed Jul 21, 2004 11:49 am

That's interesting partitioning the array like that, never thought to do it that way. Thanks, I think I can get it up to 15k sorts per second now Smile

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members