Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: arranging items in a array with a sorted pointer-list Date: Sun, 29 Nov 2020 18:58:21 -0800 Organization: A noiseless patient Spider Lines: 97 Message-ID: <86eekbpn3m.fsf@linuxsc.com> References: <87a6v02vje.fsf@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="8d063415095a95402c287fb3f3d379d0"; logging-data="3286"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/JHqkOvq+v8X8feaLW/XmOTYhtBufj8RM=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:zYbhUEvVDOdYjJogq28gwpY2QR4= sha1:a7nlkAamVRXQSNjOl6ixtg2Dkbo= Xref: csiph.com comp.lang.c:156821 Ben Bacarisse writes: > Siri Cruise writes: > >> In article , >> Bonita Montero 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 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> 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> 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> 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.