To: linux-kernel@vger.kernel.org
From: hpa@zytor.com (H. Peter Anvin)
Subject: Re: [patch 1/13] Qsort
Date: Mon, 24 Jan 2005 17:10:16 +0000 (UTC)
Organization: Mostly alphabetical, except Q, which We do not fancy
Message-ID: <ct3a5o$n0e$1@terminus.zytor.com>
References: <20050122203326.402087000@blunzn.suse.de> <Pine.LNX.4.61.0501230357580.2748@dragon.hygekrogen.localhost> <20050123044637.GA54433@muc.de> <Pine.LNX.4.61.0501230600070.2748@dragon.hygekrogen.localhost>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7BIT
NNTP-Posting-Date: Mon, 24 Jan 2005 17:10:16 +0000 (UTC)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2284
Lines: 74

Followup to:  <Pine.LNX.4.61.0501230600070.2748@dragon.hygekrogen.localhost>
By author:    Jesper Juhl <juhl-lkml@dif.dk>
In newsgroup: linux.dev.kernel
>
> On Sun, 23 Jan 2005, Andi Kleen wrote:
> 
> > > How about a shell sort?  if the data is mostly sorted shell sort beats 
> > > qsort lots of times, and since the data sets are often small in-kernel, 
> > > shell sorts O(n^2) behaviour won't harm it too much, shell sort is also 
> > > faster if the data is already completely sorted. Shell sort is certainly 
> > > not the simplest algorithm around, but I think (without having done any 
> > > tests) that it would probably do pretty well for in-kernel use... Then 
> > > again, I've known to be wrong :)
> > 
> > I like shell sort for small data sets too. And I agree it would be 
> > appropiate for the kernel.
> > 
> Even with large data sets that are mostly unsorted shell sorts performance 
> is close to qsort, and there's an optimization that gives it O(n^(3/2)) 
> runtime (IIRC), and another nice property is that it's iterative so it 
> doesn't eat up stack space (as oposed to qsort which is recursive and eats 
> stack like ****)...
> Yeah, I think shell sort would be good for the kernel.
> 

In klibc, I use combsort:

/*
 * qsort.c
 *
 * This is actually combsort.  It's an O(n log n) algorithm with
 * simplicity/small code size being its main virtue.
 */

#include <stddef.h>
#include <string.h>

static inline size_t newgap(size_t gap)
{
  gap = (gap*10)/13;
  if ( gap == 9 || gap == 10 )
    gap = 11;

  if ( gap < 1 )
    gap = 1;
  return gap;
}

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *))
{
  size_t gap = nmemb;
  size_t i, j;
  char *p1, *p2;
  int swapped;

  do {
    gap = newgap(gap);
    swapped = 0;

    for ( i = 0, p1 = base ; i < nmemb-gap ; i++, p1 += size ) {
      j = i+gap;
      if ( compar(p1, p2 = (char *)base+j*size) > 0 ) {
        memswap(p1, p2, size);
        swapped = 1;
      }
    }
  } while ( gap > 1 || swapped );
}
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/