sorting algorithm*

I'm putting my money on introsort right but I'm not sure if there is anything faster.

right now, but*

OOOOH, you hit on one of my favorite topics!

Introsort is a combination of two very good sorts, quicksort & heapsort. Most people consider quicksort to be the fastest, and it typically is very fast. It does have some weaknesses, and so it's not one of my favorites.

On the other hand, heapsort IS one of my favorites. It's usually as fast as quicksort, without the weaknesses. It's a more complicated algorithm, though.

Finally, my favorite sort is mergesort. It's the "fastest", but that is a bit misleading: it typically performs less comparisons than either of the other two (which is the standard test of speed), but it uses extra memory, and so takes actual physical time to access memory a lot.

So, in theory, mergesort, but since you're probably asking about physical time, introsort is just fine.

By the way, you can look up sorting algorithms on wikipedia, there's a whole collection of them: http://en.wikipedia.org/wiki/Category:Comparison_sorts . I don't know how much you know about big-O notation, but any comparison sort with O(n log n) is VERY good, and, in fact, is the fastest ANY comparison sort can be.

Well then, by that logic, it's fastest to do it in Python.

nuh uh! with python you're just going to keep crashing into the ceiling!

You can just import open sky.

^^^^ this one needs to be done in Java.

Thanks DeWayne Mann, very big help. I think I will go with intro for the sake of physical time as you mentioned. It's an assignment the prof is grading as a contest, the fastest sorts get extra credit.

I have learned enough about big-O to avoid the n^2's.

Do you know a site that gives an example of introsort code? If not, no worries, I'll dig for it, but if you know one off hand I'd love to know, because wiki doesn't seem to have it like they do for the other sorts.

Well, you should be able to find code for quick sort & heap sort. Then, all you do is, after running quick sort a certain number of times (and that's up to you), switch to heapsort.

So, in psuedocode, it would be like:

def introsort: { for (int i = 0; i

Oops, I'm dumb.

def introsort{

for (int i = 0; i < 10;i++){

run a quicksort pass}

while (unsorted) {

run heapsort}

}

Awesome, thanks.

I should add that you should play around with the value in the for loop. I picked 10 at random.

The general idea is, while quicksort is normally good, it is VERY slow on "nearly sorted" input. There are a number of workarounds for this, but none of them are perfect.

On the other hand, heapsort runs pretty fast on "nearly sorted" input. Thus, you want to run quicksort until the input is nearly sorted, then switch over to heap to run on that.

There is an alternative method, which is what I personally do when I have to use quicksort. It's like introsort, only, instead of using heapsort at the end, I use insertion sort. It's the same idea: insertion sort is typically very bad....except on nearly sorted input, in which case it is VERY good. You may want to try that, as well.

Ah... sounds good, will do. I'll try a couple different things and see how they compare.

Alright DeWayne Mann, I have another question for you if you don't mind. I'm still pretty new to coding so I'm probably about to embarrass myself, but anyways:

How exactly would I indicate "unsorted"?

Because I was planning on using recursion or something until it was sorted (I'm just learning sorting so I might sound silly)

...and I suppose I can't use recursion if I'm using two sorts? I don't know, the examples on wiki were hard for me to understand. If you're sick of helping me I'll buckle down and do some trial and error. :P

Well, this goes back to big O notation, but a linear search through an array takes O(n) time. Thus, you can safely tack a search on to any sort without adding too much time.

Thus, the easiest way is to write a method:

boolean isSorted(Array n) {

boolean returner = true;

for (int i = 0; i < n.size-1; i++) {

if (n[i] > n [i+1]) {

returner = false;

}

}

return returner;

}

BUT, it turns out, you don't even need to do that in this case. Where I wrote "while (unsorted)", that was more to demonstrate what was going on. heapsort will actually sort input on ONE pass (unlike quicksort, which takes many passes to work, though they all individually run quickly). thus, that while loop shouldn't even exist. just run heapsort.

for insertion sort you might need to do a little checking, though. it depends on how you write it.

(oh, and sorry if my code is a little wrong, syntax wise. i mostly code in python now, and the syntax there is a LOT different from java, and I keep getting the two confused when I switch back and forth. you get the idea though)

Oh, you can ALWAYS use recursion. Recursion is our friend!

It's just not that helpful here.

Alright cool, I'll get to writing it and let you know if I run into any problems. Thanks again for the help.

No problem. Like I said, sorting algorithms are one of my favorite topics, so I'm always willing to talk about them.

intro sort? never heard of it... i know quick and heap tho...

then again there is a radix sort if you kow the range of values is small...

wow - both you guys learning to code... and me working for a computer company with one other develpoer and a dba...

you guy betters get good :p

Duane, I know it's been awhile since we've talked...but I'm graduating with my BA in Computer Science (and Math) in a month.

And I hate radix sort. Bucket sort is SO much better in that situation :P

ouch :( the place i work is a startup - not sure we will be hiring anyone that soon =\

might be good to stay in touch tho :) gl anyway :)

well, I've got an internship for this summer. Programming for the American National Corpus, but I don't know anything more than that.

here's the website for that: http://www.americannationalcorpus.org/

Hey duane! Yeah crazy huh...after a couple years of milling about I've finally settled into the comp sci major. I don't know much about radix but I do know the algorithm is going to be tested on a huge array.