On Fri, 18 May 2001, Ng Wei Gee wrote:
> Hi all!
>
> This is not exactly Palm related, but hope someone can help me out.
>
> I've a partially sorted list and I want to sort it out completely. Which of
> these would be the most efficient in this case?
>
> - quicksort (works well for random list, but partially sorted??)
The closer to completely sorted a list is, the better quicksort works.
Quciksort is actually quite dreadful at sorting a list that's almost in
reverse order.
So for a partially sorted list, quicksort is probably your best bet -
except for the fact that quicksort is a recursive algorithm, which chews
up your stack space rather quickly (which you don't have a lot of on the
palm).
> - insertion sort (I know very little abt this)
> - bubble sort (the only sort that can stop prematurely when the list is
> fully sorted, but slow!)
There is never a good reason to use bubble sort. Avoid it like the plague!
Most sorting algorithms will happily stop when the list is fully sorted;
the only ones I can think of that don't are mergesort and heapsort.
For a partially sorted list, I'd go with quicksort unless the list is
large enough that stack space becomes an issue - then you might be best
dropping back to something like insertion sort (which is basically just a
less silly variant on bubble sort).
To dependably sort a list which might be all over the place, then heapsort
is a good bet on faster devices, however it always runs to completion
which would be grossly inefficient on a slow processor like the palm's. If
you list is not necessarily in almost-order, maybe take a look at *gulp*
shell sort?
HTH
- Andrew
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palmos.com/dev/tech/support/forums/
