Path: csiph.com!x330-a1.tempe.blueboxinc.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, 06 Jun 2011 18:10:34 -0500
Message-ID: <4DED5E6F.32F4@mindspring.com>
Date: Mon, 06 Jun 2011 19:10:39 -0400
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,comp.programming
Subject: Re: efficient or clever way
References: <70c4add5-a342-40b8-b037-079b1bedc153@x3g2000yqj.googlegroups.com> <4DECC653.2C1C@mindspring.com> <eLKdnWcU2MKPvHDQnZ2dnUVZ8oGdnZ2d@giganews.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 118
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.154.219.147
X-Trace: sv3-ZanpIMSOi8sEHpznzitXNASxQEARMMLLkMMvppMEWXS0ZSgWtDNwSaLjQ01qO7hNWsk4YTm5YP+1cod!nRFNE7tQ0WoKlP8HF3jIdnCda0JhvNqVSluClzv6G7k+XW1DbMkdYoPwe2zYk1GkTPTNKH6Fh8uW!HuU0vOiASCs=
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: 4227
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:5590 comp.programming:415

Voice Of Truth wrote:
 
> Pete, your answers are always as short as irritating.

sfsort is my latest microoptimization of
a Leapfrogging Samplesort function
with a qsort type interface.

http://www.springerlink.com/content/p70564506802n575/

/* BEGIN sfsort.h */

#ifndef H_SFSORT_H
#define H_SFSORT_H

#include <stddef.h>

void sfsort(void *base, size_t nmemb, size_t size, 
            int (*compar)(const void *, const void *));

#endif

/* END sfsort.h */



/* BEGIN sfsort.c */

#include "sfsort.h"

static void sfrog(size_t s1, 
                  size_t ss, 
                  unsigned char *A, 
                  size_t u,
                  size_t size, 
                  int (*compar)(const void *, const void *));

void            
sfsort(void *base, size_t nmemb, size_t size, 
       int (*compar)(const void *, const void *))
{
    size_t s;

    if (nmemb > 1) {
        for (s = 1; nmemb - s > s; s += s + 1) {
            sfrog(0, s - 1, base, s + s, size, compar);
        }
        sfrog(0, s - 1, base, nmemb - 1, size, compar);
    } 
}

static void 
sfrog(size_t s1, size_t ss, 
     unsigned char *A, size_t u, size_t size, 
     int (*compar)(const void *, const void *))
{
    if (s1 - ss != 1) {
        if (u > ss) {
            unsigned char *p1, *p2, *end, swap;
            const size_t  sm = (ss - s1) / 2 + s1;
            const size_t sms = sm * size;
                  size_t   j = (u + 1) * size;
                  size_t   i = ss * size;

            do {
                i += size;
            } while (j > i && compar(A + sms, A + i) > 0);
            do {
                j -= size;
            } while (j > i && compar(A + j, A + sms) > 0);
            while (j > i) {
                p1  = A + j;
                p2  = A + i;
                end = p2 + size;
                do {
                    swap  = *p1;
                    *p1++ = *p2;
                    *p2++ = swap;
                } while (p2 != end);
                do {
                    i += size;
                } while (j > i && compar(A + sms, A + i) > 0);
                do {
                    j -= size;
                } while (j > i && compar(A + j, A + sms) > 0);
            } 
            if (j == i) {
                j -= size;
            }        
            i = ss * size;
            if (j > i) {
                end = A + sms;
                p1  = A + j + size;
                p2  = A + i + size;
                do {
                    swap = *--p2;
                    *p2  = *--p1;
                    *p1  = swap;
                } while (p2 != end);
                j /= size;
                i = sm + j - ss + 1;
                sfrog(s1, sm - 1, A, i - 2, size, compar);
            } else {
                j = ss;
                i = sm + 1;
            }
            sfrog(i, j, A, u, size, compar);
        }
    } else {
        sfsort(A + s1 * size, u - ss, size, compar);
    }
}

/* END sfsort.c */


-- 
pete