Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!news.glorb.com!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: Sun, 08 Jan 2012 06:26:36 -0600
Message-ID: <4F098B7F.3544@mindspring.com>
Date: Sun, 08 Jan 2012 07:26:39 -0500
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
Subject: Re: Is there any way to refer to another array in qsort's compare function?
References: <f7d05964-b7de-45b1-afde-7ac9d7c38e9b@x34g2000prb.googlegroups.com> <0.7769aa1f0654775b9623.20111229115814GMT.87ehvnd1yh.fsf@bsb.me.uk> <5639758.1331.1326008442906.JavaMail.geo-discussion-forums@prnp7>
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
Lines: 123
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.154.218.183
X-Trace: sv3-mHvT87HLPCCdGruRaadmQ6j1bPxuqpbv/JB+MTUyxcW7SAWIuEmDGA0eOOu8xsyS1Noa2pZ8hPer/L/!gaOF9BX7pjj1qpkAX2BDGpL71Dg8j1Jv+qUEJ50LqOY5Efaez5ZCf2XFd7yUvLVS24rrCn27tNci!jtzj/vLpJBI=
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: 5271
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:15581

88888 Dihedral wrote:
> 
> Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14秒寫道：
> > Stone <ston...@gmail.com> writes:
> >
> > > Here's the problem.
> > >
> > > I wrote a function 'int my_compare(const void *, const void *);' and
> > > passed it to qsort() of stdlib.h, in order to sort an array named
> > > *ptr* which contains indices of another array *data*. By that I
> > > intended to sort elements of *ptr* (i.e. ptr[i]) using data[ptr[i]] as
> > > the key value.
> > >
> > > However, the *data* array was defined as static in main(), and seemed
> > > not easy to access in my_compare(). Is there any way to achieve this?
> >
> > You can either move the array so that it is defined at file scope
> > (i.e. outside main) or you can arrange for there to be a file-scope
> > pointer to it:
> >
> >   #include <stdlib.h>
> >   #include <stdio.h>
> >
> >   int *aux_sort_ptr;
> >
> >   int my_compare(const void *p1, const void *p2)
> >   {
> >       const int *ip1 = p1, *ip2 = p2;
> >       return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
> >   }
> >
> >   int main(void)
> >   {
> >       static int data[] = { 3, 1, 2 };
> >       int idx[] = { 1, 2, 3 };
> >       aux_sort_ptr = data;
> >       qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
> >       for (int i = 0; i < sizeof idx/sizeof *idx; i++)
> >            printf("idx[%d] = %d, data[%d] = %d\n",
> >                   i, idx[i], idx[i], data[idx[i]]);
> >   }
> >
> > This is ugly (and problematic in threaded code), but there's no elegant
> > way round it using standard C.  Many systems have other sort functions
> > whose comparison function can be handed another void * (see Dr Nick's
> > reply) but I don't think and have become common enough to though of as
> > "almost standard".
> >
> > --
> > Ben.
> 
> This will turn the quick sort algorithm to be of O(nlog(n)) in speed
> and O(n) used for the heap space.

First of all, 
whether or not qsort uses the quicksort algorithm, 
is up to the implementation.

Second, 
quicksort can be implemented with O(1) use of memory.

#include <stddef.h>
#include <limits.h>

void 
q_sort(void *base, size_t nmemb, size_t size, 
       int (*compar)(const void *, const void *))
{
    unsigned char *left;
    size_t middle, last, right;
    struct {
        size_t bytes;
        void *base;
    } stack[CHAR_BIT * sizeof nmemb], *stack_ptr;
    unsigned char *p1, *p2, *end, swap;  
 
    stack -> bytes = nmemb * size;
    stack -> base  = base;
    stack_ptr = stack + 1;
    do {
        --stack_ptr;
        if (stack_ptr -> bytes > size) {
            right = stack_ptr -> bytes - size;
            left = stack_ptr -> base;
            last = middle = 0;
            do {
                middle += size;
                if (compar(left, left + middle) > 0) {
                    last += size;
                    p1 = left + middle;
                    p2 = left + last;
                    end = p2 + size;
                    do {
                        swap  = *p1;
                        *p1++ = *p2;
                        *p2++ = swap;
                    } while (p2 != end);
                }
            } while (middle != right);
            p1 = left;
            p2 = left + last;
            end = p2 + size;
            do {
                swap  = *p1;
                *p1++ = *p2;
                *p2++ = swap;
            } while (p2 != end);
            if (right - last > last) {
                stack_ptr   -> base  = last + size + left;
                stack_ptr++ -> bytes = right - last;
                stack_ptr   -> base  = left;
                stack_ptr++ -> bytes = last;
            } else {
                stack_ptr++ -> bytes = last;
                stack_ptr   -> base  = last + size + left;
                stack_ptr++ -> bytes = right - last;
            }
        }
    } while (stack_ptr != stack);
}

-- 
pete