Which sorting algorithm?

nodger · 01-27-2005, 05:16 AM

I need a sorting algorithm that doesn't take long if the set is nearly sorted already, does qsort and mergesort do this?

ilikejam · 01-27-2005, 06:36 AM

A bubble sort might be the thing. Overall, it's rubbish, but it gets quite fast near the end of the sort. I think it might have the edge over a quicksort.

Dave

jtshaw · 01-27-2005, 07:33 AM

I would use a merge sort or a quick sort personally, but performance is highly dependant on how the data happens to fall.

I've found in real world performance the bubble sort rarely, if ever, will touch the performance of merge sort or quick sort, though I'm sure with some specifically structured datasets we could show bubble sort to be quite fast.

jim mcnamara · 01-27-2005, 09:47 AM

Your best solution:
try a known C library function like qsort, first. You are less likely to have problems later on. qsort has been beat on for 15+ years. Most of the problems have long since been chased out.

Test it on real data, not programmer data. If it works okay, don't worry about squeezing an extra five seconds off run-time. It is not worth your time.

If you are in a big production environment, look for commercial libraries like syncsort. Don't try to write a linear time sort on your own.

nodger · 01-28-2005, 06:26 AM

The set would be something like this:

1 3 6 8 11 12 16 22 25 30 31 32 35 37 41 7 15 44 2

IE. Theres 20 numbers and the first 15 are sorted but the remaining 5 are still jumbled.
In reality it might be the first 99% of them are sorted, or something like that. I'm not in a big production enviornment, so I can't afford commercial licences.

jim mcnamara · 01-28-2005, 01:40 PM

try qsort().

gamehack · 01-28-2005, 06:13 PM

Check this out

http://www.cplusplus.com/ref/cstdlib/qsort.html