NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/lang/c/12298

Text File | 1992-08-13 | 1.9 KB | 50 lines

Newsgroups: comp.lang.c
Path: sparky!uunet!gumby!destroyer!gatech!hubcap!mjs
From: [e-mail] (M. J. Saltzman)
Subject: Re: sort routines
Message-ID: <[e-mail]>
Organization: Clemson University, Clemson SC
References: <[e-mail]>
Date: Thu, 13 Aug 1992 20:11:57 GMT
Lines: 39

In article <[e-mail]> [e-mail] (Paul Keddie) writes:
>
>How do people sort a single linked list in a C program ? I know there
>is thw qsort routine but that seems to assume you know the maximum possible
>size of the list.
>
>Do you just have to resort to writing your own routine, and if so which is the
>best for a single linked list data structure (insertion,bubble.etc).

If you want to actually sort the linked structure, you need to write a
merge or bucket sort to do it (insertion sort would work, but is
probably slower--insertion sort is what you would do if you built the
list in sorted order to begin with).

On the other hand, what about creating an array of pointers to
elements of the list, and running qsort() on it, then rebuilding the
list?  Yes, you need to know how many elements are in the list, but
only at the moment you do the sort.  You can malloc() the space for
the array at that point.

If its a big list, or you are sorting it frequently or searching it
frequently, you might think about using some other data structure
(like a tree), or using a heuristic to cut down on access times in an
unsorted list (such as moving the most recently accessed element to
the front), depending on the characteristics of the list access
requests.

>Cheers Paul
>Software Maintenance Group, Software Technology Division, BT
>Research Labs, Martlesham Heath, Ipswich, IP5 7RE, UK
>E-mail:  [e-mail]
>Phone:  [phone]
>Fax:    [phone]


--
        Matthew Saltzman
        Clemson University Math Sciences
        [e-mail]