Kirupa QuickSort

[MichaelxxOA]

Now to start off I have a few disclaimers.

1. I did not know where to put this thread.. I figured this'd be a good place.
2. I mean this with NO disrespect to Kirupa, and I mention this ONLY for the sake of making this site what it is, a legit resource.

Okay so the quicksort tutorial is AWESOME I love it, Kirupa my hats off on how you explained quicksort I truly enjoyed it.

With that said I believe that it should be strongly noted that although all of the information is true, it's not necessarily the best option in Actionscript, and this is the reason.

In languages that are not actionscript and are of the type that fit what I'm talking about (yeah way to be specific right?), you have alot more access to the machine, this access is very important when it comes to algorithms and what is efficient or not

In Actionscript your data structure is the Array, the Array is both a Vector and a Hashtable.. the Vector being an actual comparison to Vectors and the Hashtable through being by default an object which is a Hashtable... it's important to note this ONLY because it shows that Arrays in Actionscript are implemented on a level lower than the Virtual Machine, meaning that methods of the Array class are executed not be a series of commands interpreted by the virtual machine but by the OS manipulating that data directly.

This means that if you call the myArray.sort() method, there is not a large series of bytecode for the VM to interpret it is handled by the Virtual Machine directly (possibly lower), equating in much smaller execution time than that of the sorting algorithm written in Actionscript.

This can be tested using K-Man's sorting algorithm and a timer... copy paste the following code into an .fla and test:

//
// Example
//
arrayInput = [6358, 6850, 1534, 3928, 9766, 3822, 1025, 7616, 106, 117, 1569, 2882, 1627, 726, 429, 2234, 7804, 7562, 3640, 1905, 3458, 3242, 2270, 251, 23, 6358, 7719, 2762, 2507, 3335, 1947, 7535, 6249, 4139, 5012, 6792, 2967, 3254, 1823, 1653, 8856, 2278, 3309, 7754, 1267, 9631, 9300, 5431, 764, 4452, 5842, 9347, 8269, 1037, 257, 9299, 2282, 5002, 449, 3533, 1120, 926, 1270, 8210, 4453, 5849, 7275, 2985, 1825, 4173, 5948, 8364, 2651, 6105, 7632, 1334, 494, 7669, 3816, 6339, 5693, 1410, 7496, 6238, 1848, 9332, 8707, 6575, 2810, 2267, 5913, 9436, 4778, 472, 1823, 1972, 105, 889, 3421, 7885, 5221, 2982, 2808, 9737, 3318, 9093, 8105, 6787, 2880, 3779, 4118, 1783, 5397, 5928, 5534, 3744, 2054, 1237, 9087, 3638, 8523, 3062, 6820, 7450, 6153, 2789, 3564, 3289, 5246, 9834];

var time = getTimer();
quickSort(arrayInput, 0, arrayInput.length-1);
trace( "Time: " + (getTimer() - time) );

time = getTimer();
arrayInput.sort();
trace( "Time: " + (getTimer() - time) );




function quickSort(arrayInput, left, right) {
    i = left;
    j = right;
    pivotPoint = arrayInput[Math.round((left+right)*.5)];
    // Loop
    while (i<=j) {
        while (arrayInput[i]<pivotPoint) {
            i++;
        }
        while (arrayInput[j]>pivotPoint) {
            j--;
        }
        if (i<=j) {
            tempStore = arrayInput[i];
            arrayInput[i] = arrayInput[j];
            i++;
            arrayInput[j] = tempStore;
            j--;
        }
    }
    // Swap
    if (left<j) {
        quickSort(arrayInput, left, j);
    }
    if (i<right) {
        quickSort(arrayInput, i, right);
    }
    return;
}

Again though, with this said I believe that it is very important to read and understand this tutorial thoroughly because it will give you an understanding as to how data is manipulated, I'd just suggest thinking over whether or not to use it in your production work.

Anyway Kirupa I love what you do here, you know I mean this with only the best of intentions... if anyone has questions (because I'm at work late and tired, and probably didn't explain this to the fullest) please ask.

Take care.
Michael

[MichaelxxOA]

I should mention that the test will show you a result of myArray.sort() being less than half the time to execute then the algorithm.

Michael

[kirupa]

I'll include a pointer to this on the last page Like I (should have) mentioned in the last page, the built-in sort is faster.

[simplistik]

How dare you MichaelxxOA!!!!!! Such disrespect... where's that ban button!!!!

j/k

Actually what's quick sort? Not able to find what you're talkin about

[McGuffin]

I can't find it either. Did a search through Firefox on the tutorial page for "sort" and it only pulled up one tutorial that had nothing to do with this.

[Jeff Wheeler]

Wow… you're absolutely correct.

Many compliments to you.

[MichaelxxOA]

Lol, I still say everyone reads the tutorial though Honestly kirupa I've had to listen to people lecture about these things and I've read many articles/books and this is one of the best and clearest explanations I've seen. LIke I said my hats off.

Michael

[Krilnon]

This means that if you call the myArray.sort() method, there is not a large series of bytecode for the VM to interpret it is handled by the Virtual Machine directly

There is also not a large series of explanations to go with it. What fun is a tutorial if a chunk of the explanation is missing because the logic isn't being provided by the language that the readers are guaranteed to be somewhat familiar with (or at least interested in) ?

I realize the point of your thread was not to discourage people from reading the tutorial, and I agree that it's a good idea to mention the faster method, but the point of a tutorial is not necessarily to show the most efficient way of doing something, but to teach ActionScript in general. The coding practices in Kirupa's method can be applied to areas outside of sorting, while Array.sort() is rather limited in usage.

Anyway, numerous ActionScript functions aren't coded in ActionScript, and a common reason not to code in ActionScript is because there are faster ways (C, I believe), but after the first revelation the rest aren't shocking at all.

[MichaelxxOA]

There is also not a large series of explanations to go with it. What fun is a tutorial if a chunk of the explanation is missing because the logic isn't being provided by the language that the readers are guaranteed to be somewhat familiar with (or at least interested in) ?

I realize the point of your thread was not to discourage people from reading the tutorial, and I agree that it's a good idea to mention the faster method, but the point of a tutorial is not necessarily to show the most efficient way of doing something, but to teach ActionScript in general. The coding practices in Kirupa's method can be applied to areas outside of sorting, while Array.sort() is rather limited in usage.

Anyway, numerous ActionScript functions aren't coded in ActionScript, and a common reason not to code in ActionScript is because there are faster ways (C, I believe), but after the first revelation the rest aren't shocking at all.

And I completely agree, as I mentioned several times that everyone should read the tutorial. What good is a tutorial on how to write fast sorting algorithms if they are not fast? People come onto these sites to learn things, and while the tutorial is phenominal (as I mentioned several times as well), it is a very important thing to mention.

And what weighs the information you're trying to deliver? Is it more important that they learn programming concepts (in what we can all agree is a very advanced tutorial, not everyone learns sorting algorithms early in a computer science course) or learning how the VM, which is essential to the production of your application, runs... and ways to improve your code.

I understand that you don't agree with me posting this thread, but I did it for all of the right reasons. Take care.

Michael

[kirupa]

I updated the first page with the Note on Performance and the last page with a link to this thread in one of the concluding paragraphs

[MichaelxxOA]

Looks great K. I seriously admire that you are so diligent about helping out in this community, you don't see that often at all. Michael

[simplistik]

what "tutorial" or what not are you guys referencing?

[Krilnon]

http://www.kirupa.com/developer/acti.../quickSort.htm

[Jeff Wheeler]

I think there is a grammatical mistake… it should be something like this:

Flash's built-in Array.sort() method is a variation of quicksort, and since it [is] coded at a lower level, [it] is also much faster. This tutorial aims to explain how quicksort works, and this will allow you to sort data that may be more varied than the limited set of inputs allowed by built-in sort methods such as Array.sort().

[GW02]

Heap sorts and merge sorts and binary trees are faster than quicksorts anyway...

edit: I'm on some sort of drug that makes you stupid, never mind.