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

Groups > comp.lang.c > #13348

Re: qsort returning index

Show key headers only | View raw

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<N;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<N;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 <stdlib.h>

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 <string.h>
#include <stdio.h>
#include <stdlib.h>

#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

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

Thread

qsort returning index Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-10-25 07:24 -0700
  Re: qsort returning index Gene <gene.ressler@gmail.com> - 2011-10-25 12:17 -0700
    Re: qsort returning index Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-10-26 00:45 -0700
  Re: qsort returning index pete <pfiland@mindspring.com> - 2011-11-14 21:01 -0500

csiph-web