Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.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, 14 Nov 2011 20:01:37 -0600 Message-ID: <4EC1C7FE.4BDC@mindspring.com> Date: Mon, 14 Nov 2011 21:01:34 -0500 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.lang.c Subject: Re: qsort returning index References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 271 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.217.117 X-Trace: sv3-7WKuKyIg6G4AX+hBuroFEU5Su+HqPeDPccMZpZ857tURSqVc7WQ8hnXJc6h/v63zRFplTjqXBYTRvgJ!zhHDe+HP67e7UXFB2j9jnHHEu2X2HrCu/rUMAaLDNsIDRIR0yfyEOZbZaEv9H1um9t3TFpEEK8/F!ByyTLlVxuow= 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: 8216 Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:13348 Malcolm McLean wrote: > > qsort is fine if all data is held in structures. E.g. if you want to > sort employees by salary, and you have a structure with salary and > name and payroll number, you can simply call qsort on the array. > > However if you have salaries in a parallel array, it is difficult. > It's necessary to set up a structure with salary and index numbers, > just to do the sort. > > That's why I've written this function. It's a sort that returns a list > of indices. I think it's best to keep it non-recursive and as a single > function, so I've chosen shellsort as the algorithm. > > /* > qsort function which returns the index of items sorted. > Uses Shell sort. > Params: buf - the array to be sorted > N - number of elements > size - element width > compfunc - qsort-style comparison function > Returns: malloced array with index numbers of sorted values in > original array. > */ > int *qsortindex(void *buf, int N, int size, int (*compfunc)(const void > *e1, const void *e2)) > { > int *answer; > int ciura_intervals[] = {701, 301, 132, 57, 23, 10, 4, 1}; > int i, ii, iii; > unsigned char *buff = buf; > unsigned char *tbuff; > int interval, res; > int t; > int passes; > > /* set up return array. Initally all entries are in index order */ > answer = malloc(N * sizeof(int)); > if(!answer) > return 0; > for(i=0;i answer[i] = i; > > /* temporary buffer to make data movement easier */ > tbuff = malloc(size); > if(!tbuff) > { > free(answer); > return 0; > } > > /* how many times to pass over the array ? */ > passes = (int) (log(N)/log(2.3)); > if(passes < 8) > passes = 8; > > /* i goes from negative to + 7. 0 to 7 we use the ciura intervals > */ > for(i= -passes+8;i<8;i++) > { > if(i >= 0) > interval = ciura_intervals[i]; > else > { > interval = 701; > /* if we've over 701 items to sort, use an intervals at about > 2.3 spacing */ > for(ii=0;ii<-i;ii++) > interval = (int) (interval * 2.3); > } > if(interval >= N) > continue; > > /* now we've got our interval, pass over with the sort */ > for(ii=0;ii { > t = answer[ii]; > memcpy(tbuff, buff + ii * size, size); > for(iii = ii - interval; iii >= 0; iii -= interval) > { > res = (*compfunc)(buff + iii*size, tbuff); > if(res < 0) > break; > memcpy(buff + (iii + interval) * size, buff + iii * size, size); > answer[iii+interval] = answer[iii]; > } > memcpy(buff + (iii + interval) * size, tbuff, size); > answer[iii + interval] = t; > } > } > > /* temporary buffer no longer needed */ > free(tbuff); > > return answer; > } I would be inclined to write it this way: #include void index_sort(size_t *index, void **ptr, void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { size_t n = 0; for (n = 0; n != nmemb; ++n) { ptr[n] = n * size + (char *)base; } qsort(ptr, nmemb, sizeof *ptr, compar); for (n = 0; n != nmemb; ++n) { index[n] = ((char *)ptr[n] - (char *)base) / size; } } These three paramters: (base), (nmemb), (size), correspond to the array from which the array of indexes will be derived. The (index) parameter is a pointer to the first element of an array of (nemb) number of elements of type size_t. The (ptr) parameter is a pointer to the first element of an array of (nemb) number of elements of type (void *). The (compar) parameter points to a function for sorting the array of pointers, from which the array of indexes is derived. Here is an example of usage: /* BEGIN output from new.c */ Original order of two arrays: Floats English 0.000000 zero 1.000000 one 2.000000 two 3.000000 three 4.000000 four 5.000000 five 6.000000 six 7.000000 seven 8.000000 eight 9.000000 nine Two arrays after being sorted by English string length: Floats English 1.000000 one 2.000000 two 6.000000 six 5.000000 five 4.000000 four 0.000000 zero 9.000000 nine 8.000000 eight 7.000000 seven 3.000000 three /* END output from new.c */ /* BEGIN new.c */ #include #include #include #define NMEMB(A) (sizeof (A) / sizeof *(A)) void index_sort(size_t *index, void **ptr, void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) { size_t n; for (n = 0; n != nmemb; ++n) { ptr[n] = n * size + (char *)base; } qsort(ptr, nmemb, sizeof *ptr, compar); for (n = 0; n != nmemb; ++n) { index[n] = ((char *)ptr[n] - (char *)base) / size; } } int elencmp(const void *a, const void *b) { const char ***aa = a; const char ***bb = b; size_t len_a = strlen(**aa); size_t len_b = strlen(**bb); return len_b > len_a ? -1 : len_b != len_a; } int main(void) { void *temp; size_t n; double doubles[] = { 0,1,2,3,4,5,6,7,8,9 }; char *english[] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" }; size_t *const index = malloc(NMEMB(english) * sizeof *index); void **const ptr = malloc(NMEMB(english) * sizeof *ptr); puts("\n/* BEGIN output from new.c */\n"); puts("Original order of two arrays:"); puts("Floats English\n"); for (n = 0; n != NMEMB(english); ++n) { printf("%-9f %s\n", doubles[n], english[n]); } putchar('\n'); if (index != NULL && ptr != NULL) { index_sort(index, ptr, english, NMEMB(english), sizeof *english, elencmp); free(ptr); n = sizeof doubles; if (sizeof english > n) { n = sizeof english; } temp = malloc(n); if (temp != NULL) { for (n = 0; n != NMEMB(english); ++n) { ((double *)temp)[n] = doubles[index[n]]; } memcpy(doubles, temp, sizeof doubles); for (n = 0; n != NMEMB(english); ++n) { ((char **)temp)[n] = english[index[n]]; } memcpy(english, temp, sizeof english); free(temp); puts("Two arrays after being " "sorted by English string length:"); puts("Floats English\n"); for (n = 0; n != NMEMB(english); ++n) { printf("%-9f %s\n", doubles[n], english[n]); } } } free(index); puts("\n/* END output from new.c */"); return 0; } /* END new.c */ -- pete