Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 07 Nov 2011 17:06:21 -0600
Message-ID: <4EB8646C.2472@mindspring.com>
Date: Mon, 07 Nov 2011 18:06:20 -0500
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.lang.c
Subject: Re: direct insertion sort
References: <e4ee7527-25b4-4d82-a7fa-649da14ba127@n18g2000vbv.googlegroups.com> <1243d96b-0fd6-4046-93f5-93cc11eb5e05@n18g2000vbv.googlegroups.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 73
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.156.231.11
X-Trace: sv3-NV9feEflVCceu7kE0+uxpkWVtGkJjXZecqR+1krJOsDQKBkady884gDgRzDABWHWtp12DECV5jPdXHh!7dpeuVazOitPVzf2W45LeUgvXGEM3StOqIwchWh4bEXIzHzNcGzVy446Dhz1JNwtSd61PVqWqCiu!/hgYSMwk4Q==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3154
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:12858

Malcolm McLean wrote:
 
> Now we write insertionsort. Give it exactly the same parameters as
> qsort
> 
> void insertionsort(const void *base, size_t N, size_t size, int
> (*compfunc)(const void *, const void *))

That's not exactly the same parameters as qsort.
It makes no sense for (base) 
to be a pointer to a const qualified type.


> {
>   /* code goes here */
> }
> 
> The first thing you will need to do is to cast base to an unsigned
> char *, call it cbase.
> That's just a little quirk of C, you can't
> manipulate a void *.
> To get the i'th element, write cbase + i * size.
> To copy, call memcpy (you'll need a temporary buffer for a temporary
> element, call malloc(size) to create it). To compare two elements, i
> and j, call (*compfunc)(cbase + i * size, cbase + j * size). To shift
> a large number of elements, call memmove().

To write a stable insertionsort in C 
as a function of the same type as qsort:
you don't need to use a cast,
you don't need to get the i'th element,
you don't need a temporary buffer,
you don't need to use a multiplication operator,
you don't need to copy,
you don't need to use malloc,
you don't need to use memcpy or memmove.
  


#include <stddef.h>

void 
insertionsort(void *base, size_t N, size_t size, 
              int (*compfunc)(const void *, const void *))
{
    unsigned char *cbase, *low, *high, *p1, *p2, swap;

    if (N-- > 1) {
        cbase = base;
        do {
            low = cbase;
            high = low + size;
            cbase = high;
            while (compfunc(low, high) > 0) {
                p1 = high;
                p2 = low;
                do {
                    swap = *p1;
                    *p1++ = *p2;
                    *p2++ = swap;
                } while (p2 != high);
                if (low == base) {
                    break;
                }
                high = low;
                low -= size;
            }
        } while (--N != 0);
    }
}

-- 
pete