Simple QuickSort

[kirupa]

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 (http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/9427EAAA-9522-4B26-8FDA-99344B8518AD/0/lec4.pdf)):


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

:)

[Jeff Wheeler]

Care to explain exactly how it works?

In comp sci 2 we'll learn about the sorting algorithms, but when I got pushed off the team that had to know about them for that contest (can't remember which contest, now), I never learned them.

[kirupa]

Wikipedia and the slide I linked to in the above post are more helpful, but it is too complicated to explain using text. This weekend, I will try to write a tutorial that describes how QuickSort works in greater detail.

[Jeff Wheeler]

You so didn't have that link when I posted! :lol:

Edit: And after looking at the first diagram in that presentation, I immediately remember it, and how it works. :)

[phorte]

Would u mind explaining what exactly this does, some of us arent as pro as u kirupa. :)
From fiddling with it, i figured out it will sort the numbers within the left and right indexs and leave the numbers outside of those left and right numbers as they are in the array. Would that be right? How is that usefull really??

Also, that code display was making IE6 lag really bad as i was scrolling down. but after it was out of view it was fine. Bit odd, its never done that before...

[micheeel]

What is the built-in flash array sorting command you mentioned?

[gvozden]

worth take a look

comparison of standard sort algos
http://linux.wku.edu/~lamonml/algor/sort/sort.html

customSort by Darron Schall
http://www.darronschall.com/weblog/archives/000069.cfm

[icio]

What is the built-in flash array sorting command you mentioned? ActionScript Code:

Array.sort();
Array.sortOn("objectVariable");





There are also other inputs to these functions that you might want to look up in the the LiveDocs (or F1 in Flash)

[kirupa]

aussie - I will try to have a writeup of what this does this weekend. The lag was caused by me having 1000 values stored in the example array, but I chopped off most of them. So you shouldn't see the lag anymore when scrolling :)

[logikal2]

pretty neat... we did something like that in class w/ c++, but it's refreshing to see it done in flash too :)

[phorte]

Awsome. Looking forward to having a read of that. And yeah, that code display doesnt lag anymore.

[gvozden]

Quicksort was implemented before, just like information, but Kirupa is cool to do it, we can implement any sort algorithms that it's there and known as good sorting techinque // http://proto.layer51.com/d.aspx?f=777

I hope you read Darren Schall article and algo
if you haven't here is important part
"We all know that the built-in Array sort method isn't the fastest around. The best way around the speed issue is to either build your own sorting method, or use someone else's. Prototype is a good place to start looking for code, and now you've brought that 261 milliseconds down to 127 with the qSort method, and even further down to 103 milliseconds with sortPInt. Still, I can't help but think that we can do better...

So.. thinking a bit about the problem, I've come up with my own custom sort method. At it's heart it resembles the "Bin Sort" algorithm. I was able to reduce the sorting time down to 58 milliseconds (from the original 261). Sweetness."

darren did magnificient job