Fast Sorting with Quicksort
       by kirupa | 11 July 2006

When you have a large collection of unsorted items, your choice of sort algorithms can greatly impact how long it takes to sort your items properly. There are numerous sort algorithms, but in this tutorial, I will focus on one of the fastest sort algorithms, quicksort. On average, quicksort works in n * log(n) time which is ideal for most uses.

Quicksort is known as a divide-and-conquer algorithm. What this means is, given an input, it divides the input into smaller parts before performing an operation on those parts as opposed to working on the entire input at once. One way of looking at it is that it is easier to eat food in smaller bite-size pieces as opposed to the whole thing at once.

Note on Performance

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

With that in mind, first let me provide you with the code you will need to implement quicksort in Flash:

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;

}

If you want to test the above code, copy the above code into a new Flash animation, copy and paste the following code below the above pasted code, and test it in Flash by pressing Ctrl + Enter:

//

// 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];

quickSort(arrayInput, 0, arrayInput.length-1);

trace(arrayInput);

When you test the above code, you will find that the unsorted values in your arrayInput array are properly sorted. In the next few sections I will describe how quicksort works in great detail!

Onwards to the next page!

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13