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

Groups > comp.lang.c > #15162 > unrolled thread

Is there any way to refer to another array in qsort's compare function?

Back to article view | Back to comp.lang.c

Contents

  Is there any way to refer to another array in qsort's compare function? Stone <stonekyx@gmail.com> - 2011-12-29 00:27 -0800
    Re: Is there any way to refer to another array in qsort's compare function? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-12-29 08:57 +0000
    Re: Is there any way to refer to another array in qsort's compare function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-29 11:58 +0000
      Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 04:20 -0800
        Re: Is there any way to refer to another array in qsort's compare function? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-12-29 12:37 +0000
          Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 04:48 -0800
            Re: Is there any way to refer to another array in qsort's compare function? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-12-29 12:59 +0000
              Re: Is there any way to refer to another array in qsort's compare function? Geoff <geoff@invalid.invalid> - 2011-12-29 10:09 -0800
                Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 17:50 -0800
                  Re: Is there any way to refer to another array in qsort's compare function? Geoff <geoff@invalid.invalid> - 2011-12-29 19:29 -0800
                    Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-30 00:36 -0800
                      Re: Is there any way to refer to another array in qsort's compare function? Bull in a China Blue Shop <chine.bleu@yahoo.com> - 2011-12-30 00:52 -0800
                        Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-30 02:16 -0800
                Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 18:01 -0800
              Re: Is there any way to refer to another array in qsort's compare function? James Kuyper <jameskuyper@verizon.net> - 2011-12-29 13:21 -0500
          Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-30 23:18 -0800
      Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-07 23:40 -0800
        Re: Is there any way to refer to another array in qsort's compare function? pete <pfiland@mindspring.com> - 2012-01-08 07:26 -0500
          Re: Is there any way to refer to another array in qsort's compare function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-08 12:50 +0000
            Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-08 06:02 -0800
          Re: Is there any way to refer to another array in qsort's compare function? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-01-17 12:35 +0200
    Re: Is there any way to refer to another array in qsort's compare function? Bull in a China Blue Shop <chine.bleu@yahoo.com> - 2011-12-29 05:07 -0800
      Re: Is there any way to refer to another array in qsort's compare function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-29 14:16 +0000
        Re: Is there any way to refer to another array in qsort's compare function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-29 15:29 +0000
          Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 09:33 -0800
          Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 15:40 -0800
    Re: Is there any way to refer to another array in qsort's compare function? James Kuyper <jameskuyper@verizon.net> - 2011-12-29 10:50 -0500
    Re: Is there any way to refer to another array in qsort's compare function? pete <pfiland@mindspring.com> - 2012-01-07 20:50 -0500

Page 2 of 2 — ← Prev page 1 [2]

#15882

pete <pfiland@mindspring.com> writes:
> Second, 
> quicksort can be implemented with O(1) use of memory.

If you were going to make such a statement, why stop at quicksort?

Anything which only needs to accept a bounded amount of input can 
be implemented with O(1) use of memory.

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

[toc] | [prev] | [next] | [standalone]

#15175

In article <f7d05964-b7de-45b1-afde-7ac9d7c38e9b@x34g2000prb.googlegroups.com>,
 Stone <stonekyx@gmail.com> wrote:

> 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?

MacOSX has qsort_r which passes a context pointer to qsort_r which, in turn, 
passes it to the compare. I don't know if other implementations have this.

-- 
My name Indigo Montoya.      |        Yippie-kay-yay, mother fakir.
You flamed my father.        |       I'm whoever you want me to be.
Prepare to be spanked.       |  Annoying Usenet one post at a time.
Stop posting that!           |    At least I can stay in character.

[toc] | [prev] | [next] | [standalone]

#15178

Bull in a China Blue Shop <chine.bleu@yahoo.com> writes:

> In article <f7d05964-b7de-45b1-afde-7ac9d7c38e9b@x34g2000prb.googlegroups.com>,
>  Stone <stonekyx@gmail.com> wrote:
>
>> 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?
>
> MacOSX has qsort_r which passes a context pointer to qsort_r which, in turn, 
> passes it to the compare. I don't know if other implementations have this.

It's in most modern versions of the GNU C library (apparently since
version 2.8) but it's not documented yet.  I think qsort_r is probably
close to being reliably available on *nix type systems but I don't know
about Windows C libraries.

For the record, here's the same program I posted but using qsort_r:

  #include <stdlib.h>
  #include <stdio.h>
   
  int my_compare(const void *p1, const void *p2, void *cp)
  {
      const int *ip1 = p1, *ip2 = p2, *aux_sort_ptr = cp;
      return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
  }
   
  int main(void)
  {
      static int data[] = { 3, 1, 2 };
      int idx[] = { 1, 2, 3 };
      qsort_r(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare, data);
      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]]);
  }

(compile, on modern Linux at least, with -std=c99 -D_GNU_SOURCE)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#15180

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Bull in a China Blue Shop <chine.bleu@yahoo.com> writes:
<snip>
>> MacOSX has qsort_r which passes a context pointer to qsort_r which, in turn, 
>> passes it to the compare. I don't know if other implementations have this.
>
> It's in most modern versions of the GNU C library (apparently since
> version 2.8) but it's not documented yet.

Argh!  I decided to write the missing man page and in so doing I found
the following mess:

The GNU version has prototype

  void qsort_r(void *base, size_t nmemb, size_t size,
               int (*compar)(const void *, const void *, void *),
               void *data);

I.e. the data pointer is last and gets passed as the third argument to
the comparison function.

The BSD version is

  void qsort_r(void *base, size_t nmemb, size_t size, void *data,
               int (*compar)(void *, const void *, const void *));

with the data pointer as the fourth argument which gets passed as the
first argument to the comparison function.

Microsoft decided to do this:

  void qsort_s(void *base, size_t nmemb, size_t size,
               int (*compare)(void *, const void *, const void *),
               void *data);

using the argument order of the GNU version and the comparison function
of the BSD version.

Annex K of the new C standard defines an option set of library extension
based on Microsoft's supposedly "safer" functions.  Here we find (edited
for consistency):

  errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
                 int (*compar)(const void *, const void *, void *),
                 void *data);

which follows the GNU version except for the name and the return type!
I don't know why the online documentation for Microsoft systems does not
used this version.

>  I think qsort_r is probably
> close to being reliably available on *nix type systems but I don't know
> about Windows C libraries.

So, no.  There is no widely available qsort function that takes a data
pointer.  If the documentation is right, you can't even use the
quasi-standard qsort_s with Microsoft's C library.

It's a shame that we are left with this mess.  Annex K is optional, and
is an all-or-nothing set of extensions (I may have misunderstood that)
so qsort_s is likely to languish alongside all the other _s functions.
qsort_r is functionally better that qsort -- the change is not a
mythical safety advantage.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#15189

Ben Bacarisse於 2011年12月29日星期四UTC+8下午11時29分16秒寫道：
> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
> 
> > Bull in a China Blue Shop <chine...@yahoo.com> writes:
> <snip>
> >> MacOSX has qsort_r which passes a context pointer to qsort_r which, in turn, 
> >> passes it to the compare. I don't know if other implementations have this.
> >
> > It's in most modern versions of the GNU C library (apparently since
> > version 2.8) but it's not documented yet.
> 
> Argh!  I decided to write the missing man page and in so doing I found
> the following mess:
> 
> The GNU version has prototype
> 
>   void qsort_r(void *base, size_t nmemb, size_t size,
>                int (*compar)(const void *, const void *, void *),
>                void *data);
> 
> I.e. the data pointer is last and gets passed as the third argument to
> the comparison function.
> 
> The BSD version is
> 
>   void qsort_r(void *base, size_t nmemb, size_t size, void *data,
>                int (*compar)(void *, const void *, const void *));
> 
> with the data pointer as the fourth argument which gets passed as the
> first argument to the comparison function.
> 
> Microsoft decided to do this:
> 
>   void qsort_s(void *base, size_t nmemb, size_t size,
>                int (*compare)(void *, const void *, const void *),
>                void *data);
> 
> using the argument order of the GNU version and the comparison function
> of the BSD version.
> 
> Annex K of the new C standard defines an option set of library extension
> based on Microsoft's supposedly "safer" functions.  Here we find (edited
> for consistency):
> 
>   errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
>                  int (*compar)(const void *, const void *, void *),
>                  void *data);
> 
> which follows the GNU version except for the name and the return type!
> I don't know why the online documentation for Microsoft systems does not
> used this version.
> 
> >  I think qsort_r is probably
> > close to being reliably available on *nix type systems but I don't know
> > about Windows C libraries.
> 
> So, no.  There is no widely available qsort function that takes a data
> pointer.  If the documentation is right, you can't even use the
> quasi-standard qsort_s with Microsoft's C library.
> 
> It's a shame that we are left with this mess.  Annex K is optional, and
> is an all-or-nothing set of extensions (I may have misunderstood that)
> so qsort_s is likely to languish alongside all the other _s functions.
> qsort_r is functionally better that qsort -- the change is not a
> mythical safety advantage.
> 
> <snip>
> -- 
> Ben.

Use merge sort or heap sort or enhanced radix sort. 

[toc] | [prev] | [next] | [standalone]

#15220

Ben Bacarisse於 2011年12月29日星期四UTC+8下午11時29分16秒寫道：
> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
> 
> > Bull in a China Blue Shop <chine...@yahoo.com> writes:
> <snip>
> >> MacOSX has qsort_r which passes a context pointer to qsort_r which, in turn, 
> >> passes it to the compare. I don't know if other implementations have this.
> >
> > It's in most modern versions of the GNU C library (apparently since
> > version 2.8) but it's not documented yet.
> 
> Argh!  I decided to write the missing man page and in so doing I found
> the following mess:
> 
> The GNU version has prototype
> 
>   void qsort_r(void *base, size_t nmemb, size_t size,
>                int (*compar)(const void *, const void *, void *),
>                void *data);
> 
> I.e. the data pointer is last and gets passed as the third argument to
> the comparison function.
> 
> The BSD version is
> 
>   void qsort_r(void *base, size_t nmemb, size_t size, void *data,
>                int (*compar)(void *, const void *, const void *));
> 
> with the data pointer as the fourth argument which gets passed as the
> first argument to the comparison function.
> 
> Microsoft decided to do this:
> 
>   void qsort_s(void *base, size_t nmemb, size_t size,
>                int (*compare)(void *, const void *, const void *),
>                void *data);
> 
> using the argument order of the GNU version and the comparison function
> of the BSD version.
> 
> Annex K of the new C standard defines an option set of library extension
> based on Microsoft's supposedly "safer" functions.  Here we find (edited
> for consistency):
> 
>   errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
>                  int (*compar)(const void *, const void *, void *),
>                  void *data);
> 
> which follows the GNU version except for the name and the return type!
> I don't know why the online documentation for Microsoft systems does not
> used this version.
> 
> >  I think qsort_r is probably
> > close to being reliably available on *nix type systems but I don't know
> > about Windows C libraries.
> 
> So, no.  There is no widely available qsort function that takes a data
> pointer.  If the documentation is right, you can't even use the
> quasi-standard qsort_s with Microsoft's C library.
> 
> It's a shame that we are left with this mess.  Annex K is optional, and
> is an all-or-nothing set of extensions (I may have misunderstood that)
> so qsort_s is likely to languish alongside all the other _s functions.
> qsort_r is functionally better that qsort -- the change is not a
> mythical safety advantage.
> 
> <snip>
> -- 
> Ben.

A you joking about using the lousy quicksort in the standard lib as posted
by the top post here ?

Take a look at some real applications of sorting required in the 
data compression in BWT or the DNA sequencing problem. 







problem 

[toc] | [prev] | [next] | [standalone]

#15182

On 12/29/2011 03:27 AM, Stone wrote:
> 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?

One alternative is to redefine ptr to contain pointers, rather than
indices, so instead of using data[ptr[i]] you use *ptr[i].

[toc] | [prev] | [next] | [standalone]

#15564

Stone wrote:
> 
> 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?

If you have for parameters in a function: 
     a pointer to the first element of data[]
     the number of elements in data[]
     the size of the elements in data[]
then 
you can derive an array of pointers to the elements of data[] 
and you can sort them using qsort
and you can derive a sorted array of indexes 
    from the sorted array of pointers.

/* BEGIN output from index_sort_test.c */

Array elements:    Indexed by string length: Printed by string length:

data[0] is zero    ptr[0] is 1               data[ptr[0]] is one
data[1] is one     ptr[1] is 2               data[ptr[1]] is two
data[2] is two     ptr[2] is 6               data[ptr[2]] is six
data[3] is three   ptr[3] is 5               data[ptr[3]] is five
data[4] is four    ptr[4] is 4               data[ptr[4]] is four
data[5] is five    ptr[5] is 0               data[ptr[5]] is zero
data[6] is six     ptr[6] is 9               data[ptr[6]] is nine
data[7] is seven   ptr[7] is 8               data[ptr[7]] is eight
data[8] is eight   ptr[8] is 7               data[ptr[8]] is seven
data[9] is nine    ptr[9] is 3               data[ptr[9]] is three

/* END output from index_sort_test.c */




/* BEGIN index_sort_test.c */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMEMB(A)    (sizeof (A) /  sizeof *(A))

int 
my_compare(const void *a, const void *b)
{
    const char (**const aa)[sizeof "three"] = a;
    const char (**const bb)[sizeof "three"] = b;
    const size_t len_a = strlen(**aa);
    const size_t len_b = strlen(**bb);

    return len_b > len_a ? -1 : len_b != len_a;
}

void
index_sort(size_t *index, 
           char **pointer, 
           void *base, 
           size_t nmemb,
           size_t size, 
           int (*compar)(const void *, const void *))
{
    size_t n;
    char *const array = base;
    
    pointer[0] = array;
    for (n = 1; nmemb > n; ++n) {
        pointer[n] = pointer[n - 1] + size;
    }
    qsort(pointer, nmemb, sizeof *pointer, compar);
    for (n = 0; n != nmemb; ++n) {
        index[n] = (pointer[n] - array) / size;
    }
}

int 
main(void)
{
    unsigned n;
    static char data[][sizeof "three"] = {
        "zero", "one",   "two", "three", "four",
        "five", "six", "seven", "eight", "nine"
    };
    size_t ptr[NMEMB(data)]; 
    char *pointer[NMEMB(data)];

    index_sort(
        ptr,
        pointer,
        data, 
        NMEMB(data),  
        sizeof *data, 
        my_compare
        );
    puts("\n/* BEGIN output from index_sort_test.c */\n");
    puts("Array elements:    Indexed by string length: "
         "Printed by string length:\n");
    for (n = 0; n != NMEMB(data); ++n) {
        printf("data[%u] is %-7s ",     n,          data[n]);
        printf("ptr[%u] is %-15u ",     n, (unsigned)ptr[n]);     
        printf("data[ptr[%u]] is %s\n", n,      data[ptr[n]]);
    }
    puts("\n/* END output from index_sort_test.c */");
    return 0;
}

/* END index_sort_test.c */

-- 
pete

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web