*wince* modified a quicksort?

Post #81,847

2/14/03 11:53:30 PM

I presume by which you mean translated or changed the parameter passing or some such. QuickSort is known to be both a fragile and finely-tuned algorithm. Attempts to improve it are always at the cost of some other scenario or corner case.

Wade.

Is it enough to love
Is it enough to breathe
Somebody rip my heart out
And leave me here to bleed

Is it enough to die
Somebody save my life
I'd rather be Anything but Ordinary
Please

-- "Anything but Ordinary" by Avril Lavigne.

Post #81,851

by jake123

2/15/03 12:07:44 AM

Yes... just the objects getting hamfisted around

Though I read one article that looked intriguing... gosling finds the pivot point with (lo0 + hi0) / 2... this one guy I read on the net seemed to think that using rand might provide overall better results over the long haul. It might be fun to come up with some test cases and see what happens... but in the context of my assignment, I kept it bog standard.

\r\n\r\n

I ran some tests online and the quicksort pretty much blows the rest of the sort algorithms I've seen completely out of the water. Very nice. I've got plans for that one already:)

--\r\n-------------------------------------------------------------------\r\n* Jack Troughton                            jake at consultron.ca *\r\n* [link|http://consultron.ca|http://consultron.ca]                   [link|irc://irc.ecomstation.ca|irc://irc.ecomstation.ca] *\r\n* Laval Qu\ufffdbec Canada                   [link|news://news.consultron.ca|news://news.consultron.ca] *\r\n-------------------------------------------------------------------

Post #81,857

by static

2/15/03 12:20:57 AM

Yes, it is generally very good.

Just beware of the "hammer" problem ("When all you have is a hammer, every problem looks like a nail."). For a situation with a wide variety in the consistency of the input data, QuickSort is almost always the best choice. But sometimes, when the input data is controlled a but better, there are even faster algorithms. IIRC, Heapsort is much faster with data that's already in a tree-structure, for instance. And for some types of integer data, a Radix sort is preferable.

Wade.

Is it enough to love
Is it enough to breathe
Somebody rip my heart out
And leave me here to bleed

Is it enough to die
Somebody save my life
I'd rather be Anything but Ordinary
Please

-- "Anything but Ordinary" by Avril Lavigne.

Post #81,868

by jake123

2/15/03 1:03:12 AM

Is that the one where you code after getting hammered?

Hehehe

\r\n\r\n

In all seriousness, I've no doubt that there's more than one way to skin the proverbial cat. Actually, in this particular case, I suspect that the quicksort was the best option from a generalised performance pov (lists of names), but we haven't talked about sorting too much in class yet; just a selection sort, very simple, very slow. The flip side of that lecture was binary searching... which is the next area I'm going to apply myself to. Well, after I check out the Radix sort you mention. I'd already heard about heap sort, but I gotta learn some more about it... and this is the first I've heard about radix.

\r\n\r\n

Which is cool... something to keep my brain occupied this evening.:)

--\r\n-------------------------------------------------------------------\r\n* Jack Troughton                            jake at consultron.ca *\r\n* [link|http://consultron.ca|http://consultron.ca]                   [link|irc://irc.ecomstation.ca|irc://irc.ecomstation.ca] *\r\n* Laval Qu\ufffdbec Canada                   [link|news://news.consultron.ca|news://news.consultron.ca] *\r\n-------------------------------------------------------------------

Post #81,875

by static

2/15/03 1:30:14 AM

You'd like this book.

[link|http://www.amazon.com/exec/obidos/tg/detail/-/0201510596/qid=1045290544/sr=1-6/ref=sr_1_6/002-2641123-7667255?v=glance&s=books|Algorithms in C++]

Lotsa stuff. Linked lists, binary trees, red-black trees, sorts of many kinds, graphs and graph traversals, searches - I know there's more.

Wade.

Is it enough to love
Is it enough to breathe
Somebody rip my heart out
And leave me here to bleed

Is it enough to die
Somebody save my life
I'd rather be Anything but Ordinary
Please

-- "Anything but Ordinary" by Avril Lavigne.

Post #81,927

by jake123

2/15/03 1:34:07 PM

Yeah...:)

...though right now is not really the time for me to get it... going to go up to see my family in a day or two.

Hm. I'm searching around for what kind of resources are available on the net. There's a ton of them, but digging them out is difficult. It's easy to find an algorithm once you know its name, but just finding algorithms is not so easy...

I think the Internet could use a repository of (non-patented open) algorithms, organised by type.

--\r\n-------------------------------------------------------------------\r\n* Jack Troughton                            jake at consultron.ca *\r\n* [link|http://consultron.ca|http://consultron.ca]                   [link|irc://irc.ecomstation.ca|irc://irc.ecomstation.ca] *\r\n* Laval Qu\ufffdbec Canada                   [link|news://news.consultron.ca|news://news.consultron.ca] *\r\n-------------------------------------------------------------------

Welcome to IWETHEY!