Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #12858

Re: direct insertion sort

Show key headers only | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

direct insertion sort karen tonantzin <cortesaguilar.karen@gmail.com> - 2011-11-04 07:43 -0700
  Re: direct insertion sort "osmium" <r124c4u102@comcast.net> - 2011-11-04 10:14 -0500
  Re: direct insertion sort Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-11-04 10:59 -0700
    Re: direct insertion sort pete <pfiland@mindspring.com> - 2011-11-07 18:06 -0500
  Re: direct insertion sort Martin Ambuhl <mambuhl@earthlink.net> - 2011-11-04 15:42 -0400
  Re: direct insertion sort Keith Thompson <kst-u@mib.org> - 2011-11-04 14:52 -0700

csiph-web