Turing Sorting Algorithm (Quick Sort)

[Amarylis]

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.

[smool]

Nice. Now sort 200000 numbers in 8.8 with a merge sort

[crossley7]

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.

[Tony]

code:

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

Time quicksort on that array.

[Amarylis]

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

[Tony]

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.

[Amarylis]

Yes, sorry, my bad on the wording

[Raknarg]

anyone want to explain quicksort?

[Amarylis]

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?

[Tony]

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

[Amarylis]

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?

[Tony]

Not if you have repeating elements in the list. Then any choice is the worst choice

code:

for i: 1..n-1  ar(i) := 42 end for   ar(n) := 41

[crossley7]

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

[Amarylis]

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*

[Amarylis]

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