arranging items in a array with a sorted pointer-list

[Bonita Montero]

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 ?

[Melzzzzz]

In my experience sorting list by pointer is much slower then swaps
and rearagning access order, makes slow traversal afterwards.


--
current job title: senior software engineer
skills: c++,c,rust,go,nim,haskell...

press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi
bili naoruzani. -- Mladen Gogala

[Bonita Montero]

> In my experience sorting list by pointer is much slower then swaps
> and rearagning access order, makes slow traversal afterwards.

No, that depends on the size of the items you have. I had items that
were so "heavy" (20 bytes) that sorting the pointers was faster and
with light items of 8 bytes sorting the items was faster.

[Alf P. Steinbach]

Better drop the in-place requirement. And then it's trivial. But do
consider that this adds an O(n) copying, and that sorting is just
O(n log n) in the first place.

- Alf

[Bonita Montero]

> Better drop the in-place requirement. And then it's trivial. ...

It's not because I need a certain solution but I'm just curious
about if there's an in-place solution without external memory.

[Richard Damon]

It will need at least 1 temporary location to save to, but that is enough.

[Kaz Kylheku]

On 2020-11-28, Bonita Montero <Bonita....@gmail.com> wrote:

Are the items scattered in dynamic memory, and of the same size?

Or can they be in a single, contiguous block of memory, and of variable
size? E.g.

[B ][C ][A] -> [A][B ][C ]

Firstly, literally without any external memory whatsoever, we cannot
even swap two items. Even the XOR trick for swapping objects bitwise
still requires external memory, such as a machine register. I think you
have to assume that you have enough external memory to exchange two
objects.

Are all items treated as unique, or can the solution potentially
take advantage of situations when pairs of items happen to be
bit-for-bit equivalent, not requiring a swap even if they appear
out of order through the pointer list?

All in all, this is essentially a miminal edit distance problem,
(in which only transpositions are allowed, no substitutions,
deletions or insertions):

https://en.wikipedia.org/wiki/Edit_distance

[Tim Woodall]

On 2020-11-28, Bonita Montero <Bonita....@gmail.com> wrote:

I'm not exactly sure what you're asking!

But:

N items in array. ptr is sorted.

for(i=0; i<N; i++)
{
swap(array[i], *ptr[i]);
for(y=i; y<N; y++)
if(ptr[y] == &array[i])
{
swap(ptr[y], ptr[i]);
break;
}
}

Completely untested. There's an O(N**2) search of the ptr array but O(N)
swaps.

I'm assuming than each item is very big and the number of items is quite
small otherwise why the no external memory when you've already used
extra memory with the ptr array.

[Tim Woodall]

Depends on exactly how you define 'temporary location' but:

void paws(unsigned char* a, unsigned char* b)
{
if((*a & 0x80) != (*b & 0x80)) { *a ^= 0x80; *b ^= 0x80; }
if((*a & 0x40) != (*b & 0x40)) { *a ^= 0x40; *b ^= 0x40; }
if((*a & 0x20) != (*b & 0x20)) { *a ^= 0x20; *b ^= 0x20; }
if((*a & 0x10) != (*b & 0x10)) { *a ^= 0x10; *b ^= 0x10; }
if((*a & 0x08) != (*b & 0x08)) { *a ^= 0x08; *b ^= 0x08; }
if((*a & 0x04) != (*b & 0x04)) { *a ^= 0x04; *b ^= 0x04; }
if((*a & 0x02) != (*b & 0x02)) { *a ^= 0x02; *b ^= 0x02; }
if((*a & 0x01) != (*b & 0x01)) { *a ^= 0x01; *b ^= 0x01; }
}

on x86 I think the above could be implemented using bts/btc, but you can
argue that the flag is an external bit of memory.

A hypothetical processor that can "test and jump" (aka Turing Machine)
has no external memory needed at all to do a swap.

[Siri Cruise]

In article <rpt731$i20$2...@dont-email.me>,

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);
}

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.*/
) {
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);
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));
for (int i=0; i<n; i++) N[i] = item2[i].o;
return N;
}

--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @
'I desire mercy, not sacrifice.' /|\
Discordia: not just a religion but also a parody. This post / \
I am an Andrea Doria sockpuppet. insults Islam. Mohammed

[Juha Nieminen]

In comp.lang.c++ Siri Cruise <chine...@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.

[Siri Cruise]

In article <rpvqc3$1cc$1...@gioia.aioe.org>,

Juha Nieminen <nos...@thanks.invalid> wrote:

> Ah, I love how in C you just implicitly cast from const void* to

I love how in C++ you have a billion names of cast. Even for a
strong coercion.

> Also love how the comparator function is non-static, throwing it in the
> global namespace. Better not have any other function with that name

Yeah, because it's impossible to decorate the code if you use it.

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

Yeah, because it's not like the original names are different,
part of collection of qsort utilities, only changed here for
didactism.

Fuck off, child.

[Bonita Montero]

I wanted an in-place alortihm.

[Kaz Kylheku]

On 2020-11-29, Juha Nieminen <nos...@thanks.invalid> wrote:
> In comp.lang.c++ Siri Cruise <chine...@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.

Arguably, you can do this in Your Compiler's C, not in ISO C. The
diagnostic is required by ISO C, which requires no such implicit cast to
be performed. The program is not required to successfully translate at
all.

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

In fact, stringcompare intrudes into a namespace reserved by ISO C.
Programs which introduce external names beginning with "str" invoke
undefined behavior.

This is given in the "Future library directions" section.

"Function names that begin with str, mem, or wcs and a lowercase letter
may be added to the declarations in the <string.h> header."

In practice, this doesn't happen just in the future; implementors
add their own functions, like strdup (POSIX), strcasecmp (various?),
memchr (GNU) ...

If <string.h> is included, there are additional considerations in the
use of those names, because <string.h> can introduce macros beginning
with str. So this is required:

#include <string.h>

#undef stringcompare
static int stringcompare(...)
{
...
}

--
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1

[Kaz Kylheku]

On 2020-11-29, Siri Cruise <chine...@yahoo.com> wrote:
> In article <rpvqc3$1cc$1...@gioia.aioe.org>,
> Juha Nieminen <nos...@thanks.invalid> wrote:
>
>> Ah, I love how in C you just implicitly cast from const void* to
>
> I love how in C++ you have a billion names of cast. Even for a
> strong coercion.

I love how you can wrap the C++ casts behind macros, and then
take advantage of them in code that compiles as C or C++:

#ifdef __cplusplus
#define strip_qual(TYPE, EXPR) (const_cast<TYPE>(EXPR))
#define convert(TYPE, EXPR) (static_cast<TYPE>(EXPR))
#define coerce(TYPE, EXPR) (reinterpret_cast<TYPE>(EXPR))
#else
#define strip_qual(TYPE, EXPR) ((TYPE) (EXPR))
#define convert(TYPE, EXPR) ((TYPE) (EXPR))
#define coerce(TYPE, EXPR) ((TYPE) (EXPR))
#endif

The GNU C++ compiler has a -Wold-style-cast warning option to find
places in your code where you're neglecting to use these macros.

Compile the code as C++, and the macros will catch issues, like some
change in the code that suddenly causes a convert(X, Y) call to suddenly
be stripping away a qualifier.

[Kaz Kylheku]

On 2020-11-28, Bonita Montero <Bonita....@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 ...

[Richard Damon]

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.

[Juha Nieminen]

In comp.lang.c++ Siri Cruise <chine...@yahoo.com> wrote:

> In article <rpvqc3$1cc$1...@gioia.aioe.org>,
> Juha Nieminen <nos...@thanks.invalid> wrote:
>
>> Ah, I love how in C you just implicitly cast from const void* to
>
> I love how in C++ you have a billion names of cast. Even for a
> strong coercion.

At least C++ doesn't allow you to *implicitly* cast away constness.
You can do it, but you have to do it *explicitly*, so your intent
is clear. This diminishes the possibility of bugs that happen because
of the UB caused by trying to modify const data.

> Fuck off, child.

Excellent mature argument. I'm convinced.

[Juha Nieminen]

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

[Juha Nieminen]

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?

[Richard Damon]

void * pointers may have a different represntation than most other
pointers (I think it must match char * pointers), this is to allow word
access machines to create special pointing to byte pointers.

You likely can get away with the function having a different type of
pointer than declared, as long as those pointers have the sam
representation, but then you are still running in 'Undefined Behavior'
territory unless the compiler makes special promises.

This means that you really should create your comparing function with
the right prototype, and change the pointer type in the function.

[James Kuyper]

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.