-----------------------------------

andytyk

Mon Jul 19, 2004 11:40 pm


Sorting in Turing and Returning Arrays from Function

-----------------------------------

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

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


for (i=0; i QuickBubble (sorts per second)
50 -  12500
100 -  11111
1000 -  5952
10000 -  4492
100000 -  3364


-----------------------------------

Catalyst

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

Wed Jul 21, 2004 1:26 am



-----------------------------------

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


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)