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

Groups > comp.lang.c > #27602

Re: How to apply qsort() with a parameter?

Show key headers only | View raw

Keith Thompson wrote:
> 
> rouben@shady.(none) (Rouben Rostamian) writes:
> [...]
> > Thank you everyone for your suggestions and comments.
> > I knew about GNU's qsort_r() with its extra parameter.
> > It does exactly what I need.  The reason I asked the
> > question here is that I was holding out hope that
> > there may be a way of doing something similar in
> > standard C.  From the responses it appears that it is
> > not possible.
> 
> If qsort_r() isn't already written in standard C,
> I'm sure it could be.

qsortR,
1   is usable in the same way that qsort_r is
2   is small
3   and has subquadratic worst case behavior.

I could easily come up with a faster
but larger function of the same type, 
if anyone wants to see one.

Here's qsortR:

#include <stddef.h>

void 
qsortR(void *base, size_t nmemb, size_t size, void *thunk, 
       int (*compar)(void *, const void *, const void *))
{
    size_t bytes, h, t;
    unsigned char *array, *after, *i, *j, *k;
    unsigned char *p1, *p2, *end, swap;

    if (nmemb > 1) {
        array = base;
        after = nmemb * size + array;
        nmemb /= 4; 
        h = nmemb + 1;  
        for (t = 1; nmemb != 0; nmemb /= 4) {
            t *= 2;
        }
        do {
            bytes = h * size;
            i = bytes + array;
            do {
                j = i - bytes;
                if (compar(thunk, j, i) > 0) {
                    k = i;
                    do {
                        p1  = j;
                        p2  = k;
                        end = p2 + size;
                        do {
                            swap  = *p1;
                            *p1++ = *p2;
                            *p2++ = swap;
                        } while (p2 != end);
                        if (bytes + array > j) {
                            break;
                        }
                        k = j;
                        j -= bytes;
                    } while (compar(thunk, j, k) > 0);
                }
                i += size;
            } while (i != after);
            t /= 2;
            h = t * t - t * 3 / 2 + 1;
        } while (t != 0);
    }
}

-- 
pete

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

Thread

How to apply qsort() with a parameter? rouben@shadow.(none) (Rouben Rostamian) - 2012-10-22 17:51 +0000
  Re: How to apply qsort() with a parameter? ImpalerCore <jadill33@gmail.com> - 2012-10-22 11:18 -0700
    Re: How to apply qsort() with a parameter? ImpalerCore <jadill33@gmail.com> - 2012-10-22 11:26 -0700
    Re: How to apply qsort() with a parameter? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-10-22 20:27 +0100
  Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-22 11:38 -0700
  Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 14:41 -0400
    Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 14:59 -0400
      Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-22 13:25 -0700
        Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-22 16:54 -0400
          Re: How to apply qsort() with a parameter? Robert Wessel <robertwessel2@yahoo.com> - 2012-10-22 23:25 -0500
            Re: How to apply qsort() with a parameter? James Kuyper <jameskuyper@verizon.net> - 2012-10-23 07:42 -0400
            Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 08:14 -0400
          Re: How to apply qsort() with a parameter? tom st denis <tom@iahu.ca> - 2012-10-23 07:05 -0700
            Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 10:13 -0400
    Re: How to apply qsort() with a parameter? "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2012-10-23 10:28 -0400
      Re: How to apply qsort() with a parameter? Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-10-23 10:56 -0400
  Re: How to apply qsort() with a parameter? Öö Tiib <ootiib@hot.ee> - 2012-10-22 15:30 -0700
  Re: How to apply qsort() with a parameter? rouben@shady.(none) (Rouben Rostamian) - 2012-10-23 03:52 +0000
    Re: How to apply qsort() with a parameter? Keith Thompson <kst-u@mib.org> - 2012-10-22 22:46 -0700
      Re: How to apply qsort() with a parameter? pete <pfiland@mindspring.com> - 2012-10-23 16:03 -0400
    Re: How to apply qsort() with a parameter? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-10-23 06:43 -0700

csiph-web