Simple QuickSort

talk open source
1

I noticed a lot of online examples for QuickSort involved unnecessary helper methods or took more roundabout ways of coding this. Here is a simple QuickSort based on the version outlined in the book Introduction to Algorithms (slide):

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 (pivotPoint<arrayInput[j]) {
   j--;
  }
  if (i<=j) {
   tempStore = arrayInput*;
   arrayInput[i++] = arrayInput[j];
   arrayInput[j--] = tempStore;
  }
 }
 // Swap
 if (left<j) {
  quickSort(arrayInput, left, j);
 }
 if (i<right) {
  quickSort(arrayInput, i, right);
 }
}
//
// 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];
 
quickSort(arrayInput, 0, arrayInput.length-1);
trace(arrayInput);

Of course, I think Flash’s built-in Sort function is QuickSort also, so the above is mainly for anybody who is curious as to how it works. The main advantage of QuickSort is that it runs very efficiently compared to a standard scan/compare/replace sort method.

I’ll probably write a tutorial outlining how QuickSort works, so the nerdy details might be found in it instead.

:slight_smile: