[EMAIL PROTECTED] (H. Peter Anvin) said:
[...]
> 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 );
> }
AFAICS, this is just a badly implemented Shellsort (the 10/13 increment
sequence starting with the number of elements is probably not very good,
besides swapping stuff is inefficient (just juggling like Shellsort does
gives you almost a third less copies)).
Have you found a proof for the O(n log n) claim?
I'd write as attached (careful, a local element on stack!)
/*
* shellsort.c: Shell sort
*
* Copyright (c) 2005, Horst H. von Brand <[EMAIL PROTECTED]>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
* * Neither the name of Horst H. von Brand nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <string.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
int i, j, h;
char tmp[size];
for(h = 1; h < nmemb; h = 3 * h + 1)
;
do {
h /= 3;
for(i = h; i < nmemb; i++) {
memcpy(tmp, base + i * size, size);
for(j = i - h; j >= 0 && compar(tmp, base + j * size); j -= h)
memcpy(base + (j + h) * size, base + j * size, size);
memcpy(base + (j + h) * size, tmp, size);
}
} while(h > 1);
}
--
Dr. Horst H. von Brand User #22616 counter.li.org
Departamento de Informatica Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria +56 32 654239
Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513
