Computer Science Canada

Turing Sorting Algorithm (Quick Sort)
Author:  Amarylis [ Wed May 09, 2012 8:51 pm ]
Post subject:  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.


Turing:


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) <= 1 then
        return
    end if
    var pivot : int
    var less, more : flexible array 1 .. 0 of int
    pivot := a (1)

    for i : 2 .. upper (a)
        if a (i) <= pivot then
            new less, upper (less) + 1
            less (upper (less)) := a (i)
        else
            new more, upper (more) + 1
            more (upper (more)) := a (i)
        end if
    end for
    QuickSort (less)
    QuickSort (more)
    concatenate (a, less, more, pivot)
end QuickSort

var ar : array 1 .. 9001 of int
var tmp : int
var t : int


for i : 1 .. 9001
    ar (i) := Rand.Int (100, 999)
end for
t := Time.Elapsed
QuickSort (ar)
put Time.Elapsed - t

for i : 1 .. 9001
    ar (i) := Rand.Int (100, 999)
end for

t := Time.Elapsed
for i : 1 .. 9000
    for o : i .. 9001
        if ar (i) > ar (o) then
            tmp := ar (i)
            ar (i) := ar (o)
            ar (o) := tmp
        end if
    end for
end for
put Time.Elapsed - t



And that's just a way to compare it to bubble sorting, time wise (I had accidentally put one more 0 on the number of elements, so I sorted 90,001 as opposed to 9,001. Took Quick Sort 10 seconds, and Selection sort 19 minutes)

Edit: I can't quite remember why I had made a counter, but it wasn't being used O.o. Removed it.
Author:  smool [ Wed May 09, 2012 10:18 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
Nice. Now sort 200000 numbers in 8.8 with a merge sort Wink
Author:  crossley7 [ Wed May 09, 2012 10:30 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
nice. That looks good. The next step in the program would be to make it an in-place sort (meaning you don't define new arrays within the function and just manipulate the original)

That will make the sort even faster and means you don't have to use up additional memory declaring additional arrays. It can get useful when you are having to manipulate large arrays that take up a bunch of memory.
Author:  Tony [ Wed May 09, 2012 11:06 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
code:

for j : 1 .. 90001
  ar(j) := 90001 - j
end for


Time quicksort on that array.
Author:  Amarylis [ Thu May 10, 2012 4:57 am ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
Wouldn't that just be proportional to J, which would still make it J times faster than Selection?


Well, in any case, I changed the algorithm a little bit so that it'll randomly select an array element to be the pivot (as opposed to the first element), which will cause a varying time on how long it'll take to sort stuff, but it'll also prevent it from always starting at the biggest, or smallest, array element if the array is already sorted.



Edit:
By the way Tony, with the above edit, took just over 31 seconds to sort the array


Edit 2:
Turing:
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) <= 1 then
        return
    end if
    var pivot : int
    var less, more : flexible array 1 .. 0 of int
    var p : int
    p := Rand.Int (1, upper (a))
    pivot := a (p)
    for i : p .. upper (a) - 1
        a (i) := a (i + 1)
    end for


    for i : 1 .. upper (a) - 1
        if a (i) <= pivot then
            new less, upper (less) + 1
            less (upper (less)) := a (i)
        else
            new more, upper (more) + 1
            more (upper (more)) := a (i)
        end if
    end for
    QuickSort (less)
    QuickSort (more)
    concatenate (a, less, more, pivot)
end QuickSort

var ar : array 1 .. 240 of int
var tmp : int
var t : int


for i : 1 .. 240
    ar (i) := Rand.Int (100, 999)
    put ar (i) : 4 ..
end for
put ""
t := Time.Elapsed
QuickSort (ar)
put Time.Elapsed - t, " ms"

for i : 1 .. 240
    put ar (i) : 4 ..
end for
Author:  Tony [ Thu May 10, 2012 12:10 pm ]
Post subject:  Re: RE:Turing Sorting Algorithm (Quick Sort)
Amarylis @ Thu May 10, 2012 4:57 am wrote:
but it'll also prevent it from always starting at the biggest, or smallest, array element if the array is already sorted.

Not completely true; it will simply make it much less likely for the worst case (pivoting on one element at a time, every time, essentially makes this as fast as bubble sort) to occur.
Author:  Amarylis [ Thu May 10, 2012 12:22 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
Yes, sorry, my bad on the wording Razz
Author:  Raknarg [ Thu May 10, 2012 12:48 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
anyone want to explain quicksort?
Author:  Amarylis [ Thu May 10, 2012 1:23 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
Finds a pivot point, partitions the array into 2 parts according to values that are greater than, or lesser than and equal to the pivot value. Then, makes two recursive calls until it has an array of either 0 or 1 to sort, returns the array value.

With Big-O notation, it takes O(N log N) time for it to sort, and on worst-case scenarios (i.e. repeatedly picking the biggest/smallest array element), it would take O (N) time, where N is the size of the array.


Which, I do believe is still faster than quadratic sorting methods.... I think Selection sort takes O (N^2) time?
Author:  Tony [ Thu May 10, 2012 3:44 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
To paraphrase, a single QuickSort iteration guarantees only that all the elements on the left of a pivot point are less than all the elements to the right of a pivot point. But that also happens to mean that the array is completely sorted for arrays of size 0, 1, and 2. You would keep on splitting the problem size until you get down to such guaranteed edge-cases. At that point the math works out such that the entire array is completely sorted.

The worst case though (picking the worst pivot every time, makes QuickSort run in O(N^2), no better than BubbleSort).
Author:  Amarylis [ Thu May 10, 2012 3:57 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
The statistical probability of it choosing the worst pivot point every single time when the pivot is chosen randomly in the array is negligible though, no?
Author:  Tony [ Thu May 10, 2012 5:14 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
Not if you have repeating elements in the list. Then any choice is the worst choice Wink
code:

for i: 1..n-1
 ar(i) := 42
end for
  ar(n) := 41
Author:  crossley7 [ Thu May 10, 2012 5:57 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
worst case is O (N^2) not O (N). That would be more efficient than O (N log N) time actually.

There are a few sorts with this time complexity, the other one I know of off the top of my head is a merge sort
Author:  Amarylis [ Thu May 10, 2012 7:50 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
Yeah, I took a look at the merge sort- I'm thinking about making that one as well soon. I'm considering making a Sort module for my school's Turing, my teacher seemed fairly impressed *shrugs*
Author:  Amarylis [ Fri May 18, 2012 3:02 pm ]
Post subject:  Re: RE:Turing Sorting Algorithm (Quick Sort)
crossley7 @ Wed May 09, 2012 10:30 pm wrote:
nice. That looks good. The next step in the program would be to make it an in-place sort (meaning you don't define new arrays within the function and just manipulate the original)

That will make the sort even faster and means you don't have to use up additional memory declaring additional arrays. It can get useful when you are having to manipulate large arrays that take up a bunch of memory.


I'm still not entirely sure how I'd go about doing the sorting without using additional arrays
Author:  Dreadnought [ Fri May 18, 2012 6:37 pm ]
Post subject:  Re: Turing Sorting Algorithm (Quick Sort)
Amarylis wrote:

I'm still not entirely sure how I'd go about doing the sorting without using additional arrays

Here's a nice animation that explains an implementation that is in place. Just skip to the part about "in Place Quicksort".
Author:  Amarylis [ Fri May 18, 2012 7:15 pm ]
Post subject:  RE:Turing Sorting Algorithm (Quick Sort)
Thank you, I'd been looking for a simple implementation to base my Turing code off of

:


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

Terms of Use | Privacy Policy