Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #156821
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: arranging items in a array with a sorted pointer-list |
| Date | 2020-11-29 18:58 -0800 |
| Organization | A noiseless patient Spider |
| Message-ID | <86eekbpn3m.fsf@linuxsc.com> (permalink) |
| References | <rpt731$i20$2@dont-email.me> <chine.bleu-75BFBB.17161028112020@reader.eternal-september.org> <87a6v02vje.fsf@bsb.me.uk> |
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.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web