Fast Sorting with Quicksort
       by kirupa | 11 July 2006

Let's pick up from where we left off on the previous page. This is the last page by the way!

if (left<j) {

quickSort(arrayInput, left, j);

}

if (i<right) {

quickSort(arrayInput, i, right);

}

Once you break out of the loop, you are presented with two if statements. The first if statement checks to see if the value stored by your left variable is less than j. If it is, then you call your quickSort function again with the left and right boundaries being the original vale for left and the variable j.

The second if statement checks to see if i less than the value stored by your right variable. If it is, then it calls the quickSort function with the left and right boundaries represented by your i and right variables respectively.

return;

This line of code is purely optional. If the data in your function escaped the while loop and snuck past the above two if statements, we simply end the function call. In Flash, you do not have to specify return - exiting a function is automatically taken care of when all other avenues for your function to work are exhausted.

This return does not mean that all calls of the quickSort function stop working. You may have many concurrent quickSort functions sorting various portions of your arrayInput if caught by the above two if statements. This return statement exits only this particular instance of the quickSort function.

Conclusion
Well, you have reached the end of this tutorial. There are many ways to have described how quicksort works in a fraction of the pages, but I really think the extra material really helps in understanding the details of quicksort in a relatively pain-free way!

For the most part, people will never know whether you implemented your sort algorithm using quicksort. Did you know that Flash's built-in array sort methods are a variation of quicksort, and that they are also faster? They are! Most sort methods in modern languages is some form of quicksort, but I think by understanding how quicksort really works, you can better customize your sort depending on the situation. You may not always have a simple set of data in a list or array form.

There will be times when a built-in sort method is the best solution to a problem. Every now and then, though, you will run into a situation where what you are trying to sort might not conform to the particular requirements of a language's built-in sort function. For example, in a project I was working on in C#, I was required to sort a massive amount of data stored in a hashmap-like Dictionary object. It was the solution to that, which I altered for Flash, that prompted me to write this tutorial.

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