Re: [Dev-C++] Sorting Linked Lists and Array Members

[Per W. <pw...@ia...>]

Yes, there are a number of n-log-n sorting algorithms. But there are no
algorithm better than n-log-n.

So worrying about the linear transfer times from moving list elements into
a vector of pointers and then back again can not be a time issue when
debating choices.

Next thing is that many n-log-n algorithms does require direct-access to
elements. If requiring traversals to locate the elements, then they will
no longer be n-log-n.

But a person who spends an hour or two with Google looking for different
sort algorithms and looking for specific help on sorting lists should be
able to quickly get a good view of what is recommendable solutions -
obviously taking into account if the lists are always small or if the
lists may have tens of thousands of entries where O(n^2) may be hundreds
of times slower than O(n log n).

If the OP did do as I suggested, he would be able to find the following
(or similar) information about merge-sort (quote is from wikipedia but
other sources of sorting algorithms would come to similar results):
"Merge sort is often the best choice for sorting a linked list: in this
situation it is relatively easy to implement a merge sort in such a way
that it requires only .(1) extra space, and the slow random-access
performance of a linked list makes some other algorithms (such as
quicksort) perform poorly, and others (such as heapsort) completely
impossible."

So in my previous post, I was trying to debate two different things:

The first thing I wanted to make clear was that a multipass solution (like
copying data to an array) can match a single-pass algorithm since O(n) +
O(n log n) + O (n) is still just O(n log n). And that a linked list means
objects are accessed using pointers meaning that the array only needs to
store these pointers and not the full node content.

The second thing I wanted to make clear was that the net have lots of
documentation about sort algorithms and about sorting of linked lists. So
someone who don't know what to do can get far with quite limited time
spent googling. Mailing lists and web forum are then great choices to ask
questions if someone gets stuck after having spent that initial time
reading up on a couple of available choices.

It is way easier when someone comes back and say: "I have been trying to
implement an insertion sort (since it is fast enough for my needs of no
more than 100 elements) but now are stuck trying to ..."

 /pwm

On Tue, 3 May 2011 mol...@se... wrote:

>
> > ------------ Pùvodní zpráva ------------
> > Od: Per Westermark <pw...@ia...>
> > Pøedmìt: Re: [Dev-C++] Sorting Linked Lists and Array Members
> > Datum: 03.5.2011 11:39:34
> > ----------------------------------------
> > It is very fast to walk through a linked list once and copy the element
> > pointers into an array. That is a linear operation - one extra step for
> > every extra element.
> >
> > Sorting an array taks n-log-n time which is the best possible for sorting.
> >
> > Rebuilding the linked list is one walk through the array, so linear time.
> >
> > So using an array is a good sorting method.
> >
> > Now try Google and look at bubble sort, insertion sort, merge sort, ...
>
>  Merge sort is also n*logn; in fact it's often used on arrays as well.
> The fact that sorting list in place may be slower than using temporary
> array is because it needs more cpu instructions to traverse/manipulate a
> list than an array.
>
> ------------------------------------------------------------------------------
> WhatsUp Gold - Download Free Network Management Software
> The most intuitive, comprehensive, and cost-effective network
> management toolset available today.  Delivers lowest initial
> acquisition cost and overall TCO of any competing solution.
> http://p.sf.net/sfu/whatsupgold-sd
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>