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

Amarylis

Wed May 09, 2012 8:51 pm


Turing Sorting Algorithm (Quick Sort)

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

So, if any of you are familiar with Quick Sort (and I"m guessing a good chunk of you could have probably easily done this), it's one of the more efficient methods of sorting arrays (compared to things like selection and insertion sorting). I got bored and decided to figure it out myself with Turing (I lack a hobby), and to understand the pseudocode for it. Well, I finally did, and I felt like sharing.




import Rand in "%oot/support/predefs/Rand.tu",
    Time in "%oot/support/predefs/Time.tu"

proc concatenate (var a : array 1 .. * of int, b, c : array 1 .. * of int, x : int)
    for i : 1 .. upper (b)
        a (i) := b (i)
    end for

    a (upper (b) + 1) := x

    for i : upper (b) + 2 .. upper (b) + upper (c) + 1
        a (i) := c (i - 1 - upper (b))
    end for
end concatenate


proc QuickSort (var a : array 1 .. * of int)
    if upper (a)