Battle of the Sorting Algorithms

[Mr. Analog]

I posted this on Fraga, but I thought I'd share with the rest of us:

So, I was bored and I'm in a bit of a "time for coding" mood (having been packing boxes all week) and I stumbled upon this neat page that shows the different sorting algorithms at work against each other:

Sorting Algorithms Demo
http://www.cs.bu.edu/teaching/alg/sort/demo/

I like this example in particular because it's visual, easy to see them each at work.

I was blown away by Quick Sort, it kicks butt. It makes a Heap Sort look like a frickin' bubble sort! And what are the guts of a typical Quick Sort you say? Well lookie here:
http://linux.wku.edu/~lamonml/algor/sort/quick.html

I used to do a lot of XML parsing in my last job and knowing the best way to sort things is important, so I guess that's why it got me all excited.

//Nerd Mode Off...

//Nerd Mode On (again)

Wow, I just wrote a JS version of this and it's smokin' fast...

Code Select Expand

//Quick Sort
function quickSort(numbers, array_size)
{
q_sort(numbers, 0, array_size - 1);
}

//Q Sort
function q_sort(numbers, left, right)
{
var pivot = new Number();
var l_hold = new Number();
var r_hold = new Number();

l_hold = left;
r_hold = right;
pivot = numbers[left];

while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;

if (left != right)
{
numbers[left] = numbers[right];
left++;
}

while ((numbers[left] <= pivot) && (left < right))
left++;

if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}

numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;

if (left < pivot)
q_sort(numbers, left, pivot-1);

if (right > pivot)
q_sort(numbers, pivot+1, right);
}


[Darren Dirt]

NFFG! (Nice Find, Fellow Geek!)

Over a decade ago in my first year UofA CompSci program on "Advanced Data Structures" (taught by THIS GUY*, who was super cool even back then in 1990 btw) we covered B-Trees and sorting algorithms and stuff... But I never remembered anything of the logic behind the sorts, unfortunately.

But the page you linked to, it's awesome how they describe HOW a QS works in just 3 simple sentences.


- - -

* back then he and his team of developer/math geeks had just finished their kick-ass Checkers program. A few years later, chess and backgammon. Now they're working on The Cadillac Of Poker "The Poki engine has been licensed for the entertainment game STACKED featuring Canadian poker player Daniel Negreanu." wow cool I didn't know that!

Hmmm... I wonder if Schaeffer's "GAMES" team is planning to go on a cruise this fall...

[Mr. Analog]

What's blowing me away is how I can give it an array a few thousand elements deep filled with random numbers and it sorts that puppy in no time, even in JavaScript.

[Lazybones]

I stumbled on that demo before, it is interesting stuff for sure.