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

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

arranging items in a array with a sorted pointer-list

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

Contents

  arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-28 11:00 +0100
    Re: arranging items in a array with a sorted pointer-list Melzzzzz <Melzzzzz@zzzzz.com> - 2020-11-28 10:49 +0000
      Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-28 12:12 +0100
    Re: arranging items in a array with a sorted pointer-list Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-11-28 03:21 -0800
      Re: arranging items in a array with a sorted pointer-list Richard Damon <Richard@Damon-Family.org> - 2020-11-28 08:32 -0500
        Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-28 14:49 +0100
          Re: arranging items in a array with a sorted pointer-list scott@slp53.sl.home (Scott Lurndal) - 2020-11-28 16:08 +0000
            Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-28 17:16 +0100
            Re: arranging items in a array with a sorted pointer-list Bart <bc@freeuk.com> - 2020-11-28 16:23 +0000
              Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-28 17:35 +0100
    Re: arranging items in a array with a sorted pointer-list "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2020-11-28 17:34 +0100
      Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-28 17:38 +0100
        Re: arranging items in a array with a sorted pointer-list Richard Damon <Richard@Damon-Family.org> - 2020-11-28 13:03 -0500
          Re: arranging items in a array with a sorted pointer-list Tim Woodall <news001@woodall.me.uk> - 2020-11-28 23:40 +0000
        Re: arranging items in a array with a sorted pointer-list Dolores Filandro <dolfiland8@gmail.com> - 2020-12-23 13:06 -0800
    Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-28 18:08 +0000
      Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-28 19:14 +0100
        Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-28 19:14 +0000
    Re: arranging items in a array with a sorted pointer-list Tim Woodall <news001@woodall.me.uk> - 2020-11-28 18:13 +0000
    Re: arranging items in a array with a sorted pointer-list Siri Cruise <chine.bleu@yahoo.com> - 2020-11-28 17:16 -0800
      Re: arranging items in a array with a sorted pointer-list Juha Nieminen <nospam@thanks.invalid> - 2020-11-29 09:41 +0000
        Re: arranging items in a array with a sorted pointer-list Siri Cruise <chine.bleu@yahoo.com> - 2020-11-29 02:16 -0800
          Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-29 18:32 +0000
          Re: arranging items in a array with a sorted pointer-list Juha Nieminen <nospam@thanks.invalid> - 2020-11-30 09:01 +0000
            Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-30 13:03 +0000
              Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-30 20:46 +0000
                Re: arranging items in a array with a sorted pointer-list scott@slp53.sl.home (Scott Lurndal) - 2020-11-30 21:03 +0000
                  Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-30 22:27 +0000
                    Re: arranging items in a array with a sorted pointer-list Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2020-11-30 18:14 -0700
                      Re: arranging items in a array with a sorted pointer-list James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-11-30 23:02 -0500
                      Re: arranging items in a array with a sorted pointer-list Dolores Filandro <dolfiland8@gmail.com> - 2020-11-30 20:12 -0800
                        Re: arranging items in a array with a sorted pointer-list scott@slp53.sl.home (Scott Lurndal) - 2020-12-01 15:04 +0000
                          Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-01 22:10 +0000
                            Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 22:25 +0000
                              Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-01 23:43 +0000
                            Re: arranging items in a array with a sorted pointer-list James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-12-01 23:25 -0500
                              Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-02 14:53 +0000
                                Re: arranging items in a array with a sorted pointer-list Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-12-02 07:03 -0800
                                  Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-02 23:48 +0000
                                Re: arranging items in a array with a sorted pointer-list James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-12-02 11:13 -0500
                                  Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-06 05:34 -0800
                                Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-02 16:25 +0000
                                  Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-02 23:58 +0000
                                Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-03 21:16 -0800
                      Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 07:33 +0000
                        Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-01 03:46 -0800
                          Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 17:15 +0000
                            Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-04 00:17 -0800
                          Re: arranging items in a array with a sorted pointer-list Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-12-01 10:07 -0800
                            Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-13 11:06 -0800
                        Re: arranging items in a array with a sorted pointer-list Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-12-01 07:04 -0800
                      Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-01 04:09 -0800
        Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-29 18:28 +0000
          Re: arranging items in a array with a sorted pointer-list dave_thompson_2@comcast.net - 2021-01-31 16:03 -0500
        Re: arranging items in a array with a sorted pointer-list Richard Damon <Richard@Damon-Family.org> - 2020-11-29 14:01 -0500
          Re: arranging items in a array with a sorted pointer-list Juha Nieminen <nospam@thanks.invalid> - 2020-11-30 09:05 +0000
            Re: arranging items in a array with a sorted pointer-list Richard Damon <Richard@Damon-Family.org> - 2020-11-30 07:09 -0500
            Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-30 13:06 +0000
              Re: arranging items in a array with a sorted pointer-list Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-11-30 06:28 -0800
                Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-30 15:50 +0000
              Re: arranging items in a array with a sorted pointer-list James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-11-30 10:07 -0500
                Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-30 15:26 +0000
            Re: arranging items in a array with a sorted pointer-list James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-11-30 10:02 -0500
      Re: arranging items in a array with a sorted pointer-list Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-29 12:32 +0000
        Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-11-29 18:58 -0800
      Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-29 13:52 +0100
        Re: arranging items in a array with a sorted pointer-list Dolores Filandro <dolfiland8@gmail.com> - 2020-12-23 13:56 -0800
    Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-11-28 23:41 -0800
      Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-12-05 12:23 +0100
        Re: arranging items in a array with a sorted pointer-list Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-06 16:27 -0800
          Re: arranging items in a array with a sorted pointer-list David Brown <david.brown@hesbynett.no> - 2020-12-07 11:17 +0100
    Re: arranging items in a array with a sorted pointer-list Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-29 18:34 +0000
      Re: arranging items in a array with a sorted pointer-list Bonita Montero <Bonita.Montero@gmail.com> - 2020-11-29 21:23 +0100
      Re: arranging items in a array with a sorted pointer-list Juha Nieminen <nospam@thanks.invalid> - 2020-11-30 09:10 +0000

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

#156830

On 11/30/20 8:06 AM, Ben Bacarisse wrote:
> Juha Nieminen <nospam@thanks.invalid> writes:
> 
>> Given that qsort takes a parameter of type int(*)(const void*, const void*)
>> I have to wonder how kosher it is to give it something else. I suppose it
>> will work with any pointer types, at least if you ignore the
>> warnings...
> 
> I'm not sure what you are saying here.  qsort takes void * data pointers
> and it's qsort that constructs the const void * data pointer to pass to
> the comparison function.  I'm not sure how you think qsort can "give it
> something else".

He wasn't talking about qsort() giving it something else, he was talking
about giving something else to qsort(), as it's fourth argument.

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

#156831

James Kuyper <jameskuyper@alumni.caltech.edu> writes:

> On 11/30/20 8:06 AM, Ben Bacarisse wrote:
>> Juha Nieminen <nospam@thanks.invalid> writes:
>> 
>>> Given that qsort takes a parameter of type int(*)(const void*, const void*)
>>> I have to wonder how kosher it is to give it something else. I suppose it
>>> will work with any pointer types, at least if you ignore the
>>> warnings...
>> 
>> I'm not sure what you are saying here.  qsort takes void * data pointers
>> and it's qsort that constructs the const void * data pointer to pass to
>> the comparison function.  I'm not sure how you think qsort can "give it
>> something else".
>
> He wasn't talking about qsort() giving it something else, he was talking
> about giving something else to qsort(), as it's fourth argument.

Ah, right.  I didn't think that was the case because of "ptr" in Siri's
source but it's true we didn't know.

-- 
Ben.

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

#156829

On 11/30/20 4:05 AM, Juha Nieminen wrote:
> In comp.lang.c++ Richard Damon <Richard@damon-family.org> wrote:
>> On 11/29/20 4:41 AM, Juha Nieminen wrote:
>>> In comp.lang.c++ Siri Cruise <chine.bleu@yahoo.com> wrote:
>>>> This is my code
>>>>
>>>>     int stringcompare ( /*String comparison for qsort.*/
>>>>         const ptr a, const ptr b
>>>>     ) {
>>>>         char **A = a, **B = b;
>>>>         return strcmp(*A, *B);
>>>>     }
>>>
>>> Ah, I love how in C you just implicitly cast from const void* to
>>> non-const char** without a worry in the world, happily ignoring
>>> the compiler warnings, because what does the compiler know anyway?
>>> It's just a dumb program.
>>>
>>> Also love how the comparator function is non-static, throwing it in the
>>> global namespace. Better not have any other function with that name
>>> anywhere else. But how likely is that? After all, "stringcompare" is
>>> such a unique name. The chances that anybody will ever use that same
>>> name anywhere are astronomically minuscule.
>>
>> Actually, if ptr is a typedef for void* then a 'const ptr' is a
>> 'void *const' not a 'const void*' if I remember the rules right.
> 
> Given that qsort takes a parameter of type int(*)(const void*, const void*)
> I have to wonder how kosher it is to give it something else.

You're right to wonder - passing it an argument that could not be
assigned to an object of the declared type of the parameter would be a
constraint violation (6.5.2.2p2). Such an assignment would be permitted
only if

"... (considering the type the left operand would have after lvalue
conversion) both operands are pointers to qualified or unqualified
versions of compatible types, and the type pointed to by the left has
all the qualifiers of the type pointed to by the right." (6.5.16.1p1).

In general, using incompatible function types would be seriously
problematic. However, in this particular case, the only difference is in
the location of the 'const' qualifier, so the issue gets a little more
subtle.

The 'const' that appears in a parameter declared "void * const" is
ignored for purposes of determining the compatibility of the function
types (6.7.6.3p15). However, the 'const' that appears in "const void*"
is not ignored, so those parameter types are not compatible (6.7.6.1p2),
rendering the function types not compatible (6.7.6.3p15).

It would be legal to call qsort() without #include <stdlib.h>. If you do
that, you have to provide a declaration for it, but that declaration
could be a K&$ style declaration, which would qualify as compatible with
the definition of qsort(). In that case, there is no compile-time
compatibility check. Instead, if the value passed as the fourth argument
of qsort was not compatible with int(*)(const void*, const void*), the
behavior of the call to qsort() would be undefined (6.5.2.2p6).

In practice, I would not expect the undefined behavior of such a call to
be problematic unless the function declared "int(*)(void *const, void
*const) actually took advantage of that fact by attempting to write
through the pointers, which this one doesn't, so it might work despite
the nominal incompatibility. However, I wouldn't recommend counting on that.

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

#156805

Siri Cruise <chine.bleu@yahoo.com> writes:

> In article <rpt731$i20$2@dont-email.me>,
>  Bonita Montero <Bonita.Montero@gmail.com> wrote:
>
>> Imagine you sort a list of pointers to a list of items to prevent
>> expensive swaps of the items at the first place. How could you
>> rearrange the items according to the pointer-list in place with
>> the fewest steps without any external memory ?
>
> This is my code

I think "without any external memory" is supposed to suggest an in-place
algorithm -- i.e. using only O(1) memory (excluding the original data,
of course).  You use O(n) memory.

>     int stringcompare ( /*String comparison for qsort.*/
>         const ptr a, const ptr b

What is ptr?  It is a macro for "void *"?  That seems... worrying!  And
if it's a typedef for void * then that const is qualifying the wrong
thing.

(Also, stringcompare is an identifier reserved for the implementing.  It
probably does not matter, but I prefer to avoid the issue altogether.)

>     ) {
>         char **A = a, **B = b;

I'd preserve const here: const char *const *A = a, *cost *B = b;

>         return strcmp(*A, *B);
>     }
>
>     int unsignedcompare ( /*Unsigned number comparison.*/
>         const ptr a, const ptr b
>     ) {
>         unsigned *A = a, *B = b;
>         return *A<*B ? -1 : *A>*B ? 1 : 0;
>     }
>
>     unsigned *stringorder (
>             /*Sort an array of strings. Rather than return the
>               strings, the order of sorted strings is returned.*/
>         Nat n, /*Array length.*/
>         char **list /*Array of strings.*/

You could make multiple use of const here too since you copy the
pointers and never modify the pointed-to data.

Wouldn't it be better to pass the comparison function as a parameter?

>     ) {
>        typedef struct {char *s; unsigned i;} Item1;
>         Item1 item1[n];
>         for (int i=0; i<n; i++) {
>             item1[i].s = list[i]; item1[i].i = i;
>         }
>         qsort(item1, n, sizeof(Item1), stringcompare);

I prefer to get the size the actual parameters.  That way the size can
be checked just by looking at the call:

          qsort(item1, n, sizeof *item1, stringcompare);

>         typedef struct {unsigned i; unsigned o;} Item2;
>         Item2 item2[n];
>         for (int i=0; i<n; i++) {
>             item2[i].i = item1[i].i; item2[i].o = i;
>         }
>         qsort(item2, n, sizeof(Item2), unsignedcompare);
>         unsigned *N = malloc(n*sizeof(unsigned));

I prefer unsigned *N = malloc(n * sizeof *N);

>         for (int i=0; i<n; i++) N[i] = item2[i].o;
>         return N;
>     }

Apologies for making so many remarks, but on-topic posts with C code are
so rare these days, I couldn't resist!

-- 
Ben.

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

#156821

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

> Siri Cruise <chine.bleu@yahoo.com> writes:
>
>> In article <rpt731$i20$2@dont-email.me>,
>>  Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>
>>> Imagine you sort a list of pointers to a list of items to prevent
>>> expensive swaps of the items at the first place.  How could you
>>> rearrange the items according to the pointer-list in place with
>>> the fewest steps without any external memory ?
>>
>> This is my code
>
> I think "without any external memory" is supposed to suggest an in-place
> algorithm -- i.e. using only O(1) memory (excluding the original data,
> of course).

That is what I took it to mean.

>>     int stringcompare ( /*String comparison for qsort.*/
>>         const ptr a, const ptr b
>
> [...] stringcompare is an identifier reserved for the implementi[on]

It's good to point that out, however, we don't know for sure that
the identifier 'stringcompare' here has external linkage.  Certainly
the code presented is incomplete, and there could have been a
previous declaration

    static int stringcompare( /* ... */ );

Personally I find it useful to use 'static' (for internal linkage)
on forward declarations of functions, and not at the point of
function definition.  If stringcompare() has internal linkage, and
<string.h> has not been #include'd, then there is no conflict and no
potential problem.

Like you say (in a part that was cut :(), generally it's a good idea
to avoid the problem altogether, and choose a name that does not
overlap the external linkage reserved identifier space, even for
names with internal linkage.  Still, I think it's important to be
accurate with regard to what the Standard actually specifies.

>>     ) {
>>         char **A = a, **B = b;
>
> I'd preserve const here:  const char *const *A = a, *cost *B = b;

Only the two const's after the *'s are necessary.  I wouldn't
automatically put in the first const, as I'm not sure it accurately
conveys what is meant here.  If I knew for sure that the pointers
being referred to were 'char *' rather than 'const char *' then I
probably would not put in the initial const.  Perhaps a small point
but IMO one worth considering.

>>     ) {
>>        typedef struct {char *s; unsigned i;} Item1;
>>         Item1 item1[n];
>>         for (int i=0; i<n; i++) {
>>             item1[i].s = list[i]; item1[i].i = i;
>>         }
>>         qsort(item1, n, sizeof(Item1), stringcompare);
>
> I prefer to get the size the actual parameters.  That way the size can
> be checked just by looking at the call:
>
>           qsort(item1, n, sizeof *item1, stringcompare);

I think there is another point worth making here.  The comparison
routine expects pointers to char *'s, but what it is getting (in the
form of void *'s) are pointers to Item1's.  The code will work
because the structure member holding the char * is the first member
of the struct, but it's the kind of unstated/uncommented fudge that
makes me a bit nervous.

>>         typedef struct {unsigned i; unsigned o;} Item2;
>>         Item2 item2[n];
>>         for (int i=0; i<n; i++) {
>>             item2[i].i = item1[i].i; item2[i].o = i;
>>         }
>>         qsort(item2, n, sizeof(Item2), unsignedcompare);
>>         unsigned *N = malloc(n*sizeof(unsigned));
>
> I prefer unsigned *N = malloc(n * sizeof *N);

Ditto.

>>         for (int i=0; i<n; i++) N[i] = item2[i].o;
>>         return N;
>>     }
>
> Apologies for making so many remarks, but on-topic posts with C
> code are so rare these days, I couldn't resist!

No apology necessary.  The group needs more posts like yours
here.

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

#156807

I wanted an in-place alortihm.

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

#157665

On Sunday, November 29, 2020 at 7:52:22 AM UTC-5, Bonita Montero wrote:
> I wanted an in-place alortihm.

I have a function which can sort an array of arbitrarily large elements
using two arrays of pointers for extra storage
such that:
    The sort is stable.
    There are O(N * log(N)) comparisons.
    The original array is overwritten in a single pass.

Is that something that you would be interested in seeing?

/* BEGIN ppsort.h */
/*
** Stable sort.
**
** ppsort parameters are the same as for qsort.
**
** ppsort is intended to be optimal for (size > 4 * sizeof base),
** otherwise a simple mergesort can be done using less memory.
**
** If (nmemb > 1), then
** ppsort allocates 2 objects
** each of (nmemb * sizeof base) bytes of memory
** and then calls pppsort,
** and then frees memory after.
** If (nmemb > 1) and if there is an allocation problem,
** then any allocated memory is freed,
** no sorting occurs, and the function retuns 0, 
** otherwise the function returns 1.
**
** (buff) and (ptrs) shall each point
** to the first members of two distinct nonoverlapping arrays of
** (nmemb) number of elements of type (unsigned char *).
** Last four pppsort parameters are the same as for qsort.
*/

#ifndef H_PPSORT_H
#define H_PPSORT_H

#include <stddef.h>

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

void pppsort(
        unsigned char **buff,
        unsigned char **ptrs,
        void *base, 
        size_t nmemb,
        size_t size,
        int (*compar)(const void *, const void *));

#endif

/* END ppsort.h */

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

#156798

Bonita Montero <Bonita.Montero@gmail.com> writes:

> Imagine you sort a list of pointers to a list of items to prevent
> expensive swaps of the items at the first place.  How could you
> rearrange the items according to the pointer-list in place with
> the fewest steps without any external memory ?

Do you mean a linked list of pointers, with the pointers
pointing to nodes in a linked list of items?  If not then
could you give the declarations and typedefs needed to
explain what is meant?

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

#156937

>> Imagine you sort a list of pointers to a list of items to prevent
>> expensive swaps of the items at the first place.  How could you
>> rearrange the items according to the pointer-list in place with
>> the fewest steps without any external memory ?

> Do you mean a linked list of pointers, with the pointers
> pointing to nodes in a linked list of items?  If not then
> could you give the declarations and typedefs needed to
> explain what is meant?

Everyone except you understood what I meant.

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

#157004

Bonita Montero <Bonita.Montero@gmail.com> writes:

>>> Imagine you sort a list of pointers to a list of items to prevent
>>> expensive swaps of the items at the first place.  How could you
>>> rearrange the items according to the pointer-list in place with
>>> the fewest steps without any external memory ?
>>
>> Do you mean a linked list of pointers, with the pointers
>> pointing to nodes in a linked list of items?  If not then
>> could you give the declarations and typedefs needed to
>> explain what is meant?
>
> Everyone except you understood what I meant.

Ahh, in place of an answer there is instead an ad hominem
remark.  Forgive me for thinking you actually wanted to
take part in a serious discussion.

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

#157017

On 07/12/2020 01:27, Tim Rentsch wrote:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
> 
>>>> Imagine you sort a list of pointers to a list of items to prevent
>>>> expensive swaps of the items at the first place.  How could you
>>>> rearrange the items according to the pointer-list in place with
>>>> the fewest steps without any external memory ?
>>>
>>> Do you mean a linked list of pointers, with the pointers
>>> pointing to nodes in a linked list of items?  If not then
>>> could you give the declarations and typedefs needed to
>>> explain what is meant?
>>
>> Everyone except you understood what I meant.
> 
> Ahh, in place of an answer there is instead an ad hominem
> remark.  Forgive me for thinking you actually wanted to
> take part in a serious discussion.
> 

It is how /you/ regularly respond to other people.  (Yes, I know you
have failed to understand this sort of thing before.  I'll be happy to
explain in more detail if you are interested.)

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

#156814

On 2020-11-28, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Imagine you sort a list of pointers to a list of items to prevent
> expensive swaps of the items at the first place. How could you

How is it that you have the external memory to allocate the nodes
of this list of pointers (not even an array, which is more compact)?

But, suddenly, you don't have any external memory to then
move the items into that order.

Trololollolol ...

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

#156816

> How is it that you have the external memory to allocate the nodes
> of this list of pointers (not even an array, which is more compact)?

The pointer-list might not be big, but the native objects might be.

> But, suddenly, you don't have any external memory to then
> move the items into that order.
> Trololollolol ...

I'm not trolling. I'm just curious about a difficult problem.

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

#156824

In comp.lang.c++ Kaz Kylheku <563-365-8930@kylheku.com> wrote:
> On 2020-11-28, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> Imagine you sort a list of pointers to a list of items to prevent
>> expensive swaps of the items at the first place. How could you
> 
> How is it that you have the external memory to allocate the nodes
> of this list of pointers (not even an array, which is more compact)?
> 
> But, suddenly, you don't have any external memory to then
> move the items into that order.

A pointer takes typically 4 or 8 bytes of memory. The elements of that
array to be sorted could take like 1 MB of memory each, for all we know.
The entire array could be like 10 GB in size.

Sorting in place vs. sorting from the original array to another could
mean the difference between requiring 1 MB of additional RAM vs.
requiring 10 GB of additional RAM.

> Trololollolol ...

Maybe you should think before making a fool of yourself?

[toc] | [prev] | [standalone]

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

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

csiph-web