NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/comp/lang/c/20016

Internet Message Format | 1993-01-21 | 5.2 KB

Path: sparky!uunet!spool.mu.edu!agate!dog.ee.lbl.gov!horse.ee.lbl.gov!torek
From: [e-mail] (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: qsort/pointer question (should be in FAQ?)
Date: 21 Jan 1993 14:37:35 GMT
Organization: Lawrence Berkeley Laboratory, Berkeley CA
Lines: 135
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: 128.3.112.15

In article <[e-mail]>
[e-mail] (Darrell McCauley) writes:
>>>I need to sort a 2 dimensional double array:
>>>   qsort (z, 10, 2*sizeof (double), zcmp);
>>>and I cannot figure out how to write the comparison function. ...

In article <[e-mail]>
[e-mail] (Dave Fuller) correctly points out
that `2 * sizeof(double)' is at best suspicious, and notes how two-
dimensional arrays are laid out in memory (i.e., in row major order
and *always* contiguous).  (See my previous posting on things that
are not arrays, but `act like them'; in this case some or all parts
of the arrays may not be contiguous.)

In article <[e-mail]>
[e-mail] (Darrell McCauley) provides the missing
information (see below) and asks:
>Is this the case when the array is dynamically allocated?

If a space is not contiguous, qsort cannot sort it.

Qsort *can* be used to sort a contiguous set of pointers to
discontiguous areas.  The result is sorted *pointers*, not sorted
areas.  If you do want contiguous areas, you can sort the pointers,
then copy to contiguous space; this may be faster than sorting the
areas themselves (because swapping pointers can be done more easily
than swapping large memory regions).

>According to the FAQ, you have to allocate nrows*ncolumns in one malloc
>call to get contiguous memory chunks

The is correct.

>(even then, though, are you assured of getting contiguous memory?

Yes.

>If nrows*ncolumns is too large of a chunk, won't unix split it up among
>different memory locations?).

(`Unix'?  This is comp.lang.c, not comp.unix.programmer.)  The C
language requires that malloc return at least as many bytes, as one
flat piece of memory, as requested.  If this is not available, malloc()
should return NULL.  On modern computers, the underlying memory may
reside in separate physical boxes or chips or computers, but it must
*appear* contiguous to the programmer.

>Anyway, sticking the the problem at hand, I'm doing memory allocation
>the normal way:
>
>         double **array;
>     array = (double **)malloc(nrows * sizeof(double *));
>         for(i = 0; i < nrows; ++i)
>           array[i] = (double *)calloc(ncolumns * sizeof(double));

In this case, a valid qsort call might be:

    qsort((void *)array, nrows, sizeof(double *), mycompare);

where mycompare has previously been defined as, e.g.:

    int
    mycompare(const void *a, const void *b) {
        const double *l, *r;

        /*
         * Each element of the array being sorted is a `double *'.
         * qsort passes a pointer to each element, or a `double **',
         * but encodes it in a `const void *' (a and b).  Here we
         * fetch the array elements, i.e., the row vectors.  Each
         * points to (the first element of) a column (a set of
         * `ncolumns' doubles).
         */
        l = *(const double **)a;
        r = *(const double **)b;

        /*
         * Now l points to the column currently on the left, and r
         * to the one on the right.  We want to sort rows according
         * to the value in column 0 (l[0], r[0]).
         */
        if (l[0] < r[0])
            return (-1);    /* l before r (already in order) */
        if (l[0] > r[0])
            return (1);    /* r before l (reverse them) */
        return (0);        /* order irrelevant */
    }

Dave Fuller goes on to add:
>>If you want to do a 2-d array sort (by row i assume), you are going to
>>be writing your own routines to do it.

Again, qsort can sort *anything contiguous*.  It can NOT sort disjoint
objects, such as elements of a linked list.  Merge sorts are good for
lists, but if you like, you can `arrayify' the list, sort it with
qsort, and `listify' the resulting sorted array.  In some cases, lists
are built `inside' arrays anyway---this is more common in languages
like FORTRAN, where pointers must be simulated, than in C, but it does
happen---and in these cases the sort may be `free' (discounting any
problems with holes).

Note that qsort is not guaranteed to be stable.  That is, given something
like:

    (5 tiger)
    (2 elephant)
    (1 raven)
    (2 zebra)

if you were to sort these numerically (comparing only the numbers) with
qsort, you could get either:

    (1 raven)
    (2 elephant)
    (2 zebra)
    (5 tiger)

or:

    (1 raven)
    (2 zebra)
    (2 elephant)
    (5 tiger)

A stable sort guarantees the former, in which `elephant' comes before
`zebra' because it *used to* come before zebra.

Qsort can be forced stable by the simple expedient of numbering the
elements in advance, and adding the numbers as a final sort key for
otherwise-identical elements.  Merge sorts are typically inherently
stable, which is another reason to use merge sort.  If your C library
implements qsort using a merge sort, be glad. :-)
--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE ([phone])
Berkeley, CA        Domain:    [e-mail]