Kirupa QuickSort

talk open source
1

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*<pivotPoint) {
            i++;
        }
        while (arrayInput[j]>pivotPoint) {
            j--;
        }
        if (i<=j) {
            tempStore = arrayInput*;
            arrayInput* = 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