Solution to "One Algorithm Problem"
Andrew Tomazos
<http://groups.google.com/group/comp.programming/browse_thread/thread/
f7212303f3789b37>
<http://groups.google.com/group/comp.lang.c/browse_thread/thread/
58b60dda280aaccf>
Here is my C implementation of an O(N) time, O(1) space solution to
the "one algorithm problem" of sorting an unordered array of N records
(A[]) that have unique integer keys in the range 0..(N-1), according
to an array of integers (B[]) that are a permutation of the keys of A.
I would appreciate it if someone could verify that it is correct and
indeed runs in O(N) time.
void assert(int b) { if (!b) while (1) /* hang */; }
struct V {/* satalite data */};
struct R { int key; struct V value; };
void one_algo_prob(struct R* A, const int* B, const int N)
{
int i, j, a0, b0;
for (i = 0; i < N; i++)
if (A[i].key == 0)
{
A[i] = A[0];
A[0].key = 0;
break;
}
for (i = 1; i < N; i++)
{
while (A[i].key != i)
{
A[0] = A[i];
A[i] = A[A[0].key];
A[A[0].key] = A[0];
A[0].key = 0;
}
}
for (i = 0; i < N; i++)
assert(A[i].key == i);
a0 = 0;
for (i = 0; i < N; i++)
{
if (B[i] == 0)
b0 = i;
}
assert(A[a0].key == 0);
assert(B[b0] == 0);
if (a0 != b0)
{
A[a0] = A[b0];
A[b0].key = 0;
a0 = b0;
}
assert(a0 == b0);
for (i = 0; i < N; i++)
{
j = i;
while (A[j].key != B[j])
{
A[a0] = A[j];
A[j] = A[B[j]];
A[B[j]] = A[a0];
A[a0].key = 0;
j = B[j];
}
}
for (i = 0; i < N; i++)
{
assert(A[i].key == B[i]);
}
}
int main(int argc, char** argv)
{
struct R A[10];
int B[10];
B[0] = 8;
B[1] = 2;
B[2] = 7;
B[3] = 1;
B[4] = 5;
B[5] = 0;
B[6] = 3;
B[7] = 9;
B[8] = 4;
B[9] = 6;
A[0].key = 5;
A[1].key = 9;
A[2].key = 0;
A[3].key = 8;
A[4].key = 3;
A[5].key = 4;
A[6].key = 6;
A[7].key = 7;
A[8].key = 1;
A[9].key = 2;
one_algo_prob(A,B,10);
}
Regards,
Andrew.
--
Andrew Tomazos <and...@tomazos.com> <http://www.tomazos.com>
Doug Miller
>In follow-up to these two threads:
><http://groups.google.com/group/comp.programming/browse_thread/thread/
>f7212303f3789b37>
><http://groups.google.com/group/comp.lang.c/browse_thread/thread/
>58b60dda280aaccf>
>
>Here is my C implementation of an O(N) time, O(1) space solution to
>the "one algorithm problem" of sorting an unordered array of N records
>(A[]) that have unique integer keys in the range 0..(N-1), according
>to an array of integers (B[]) that are a permutation of the keys of A.
>
>I would appreciate it if someone could verify that it is correct and
>indeed runs in O(N) time.
I'm making no comments on correctness. It definitely does *not* run in O(N)
time; both of these loops are O(N^2):
> for (i = 1; i < N; i++)
> {
> while (A[i].key != i)
> {
> A[0] = A[i];
> A[i] = A[A[0].key];
> A[A[0].key] = A[0];
> A[0].key = 0;
> }
> }
and
Andrew Tomazos
> >I would appreciate it if someone could verify that it is correct and
> >indeed runs in O(N) time.
>
> I'm making no comments on correctness. It definitely does *not* run in O(N)
> time; both of these loops are O(N^2):
Actually that would only be true if the inner loops ran an average of
N times per iteration of the outer loop, which they do not. In fact
they run an average of <1 times.
This can be demonstrated by placing a counter inside the inner loops.
Code and output included below.
The thing to remember is that the inner loop only gets executed if A
[i] is out of place. After a single iteration of the inner loop, one
more A[i] is in place that was not previously. Therefore the inner
loop can run only run a maximum of N times for the *entire* lifespan
of the outer loop. Therefore it runs an average of <1 time per
iteration of the outer loop.
Do you agree?
Thanks,
Andrew.
count_loop_1 = 0;
for (i = 1; i < N; i++)
{
while (A[i].key != i)
{
A[0] = A[i];
A[i] = A[A[0].key];
A[A[0].key] = A[0];
A[0].key = 0;
count_loop_1++;
}
}
printf("N = %d, count_loop_1 = %d\n", N, count_loop_1);
count_loop_2 = 0;
for (i = 0; i < N; i++)
{
j = i;
while (A[j].key != B[j])
{
A[a0] = A[j];
A[j] = A[B[j]];
A[B[j]] = A[a0];
A[a0].key = 0;
j = B[j];
count_loop_2++;
}
}
printf("N = %d, count_loop_2 = %d\n", N, count_loop_2);
This prints out:
N = 10, count_loop_1 = 6
N = 10, count_loop_2 = 7
Doug Miller
>On Apr 20, 1:20=A0pm, spamb...@milmac.com (Doug Miller) wrote:
>> >I would appreciate it if someone could verify that it is correct and
>> >indeed runs in O(N) time.
>>
>N)
>> time; both of these loops are O(N^2):
>
>Actually that would only be true if the inner loops ran an average of
>N times per iteration of the outer loop, which they do not. In fact
>they run an average of <1 times.
>
>This can be demonstrated by placing a counter inside the inner loops.
>Code and output included below.
>
>The thing to remember is that the inner loop only gets executed if A
>[i] is out of place. After a single iteration of the inner loop, one
>more A[i] is in place that was not previously. Therefore the inner
>loop can run only run a maximum of N times for the *entire* lifespan
>of the outer loop. Therefore it runs an average of <1 time per
>iteration of the outer loop.
>
>Do you agree?
Yeah, you're right. Missed that point about maximum of N times. Sorry.
Richard Heathfield
> In follow-up to these two threads:
>
<http://groups.google.com/group/comp.programming/browse_thread/thread/
> f7212303f3789b37>
> <http://groups.google.com/group/comp.lang.c/browse_thread/thread/
> 58b60dda280aaccf>
>
> Here is my C implementation of an O(N) time, O(1) space solution
> to the "one algorithm problem" of sorting an unordered array of N
> records (A[]) that have unique integer keys in the range 0..(N-1),
> according to an array of integers (B[]) that are a permutation of
> the keys of A.
>
> I would appreciate it if someone could verify that it is correct
> and indeed runs in O(N) time.
Unfortunately, you missed an important condition of the original
specification, to wit: "WITHOUT using any extra variable space".
<snip>
> int i, j, a0, b0;
This surely counts as extra space.
(And no, I don't see how to do it /without/ extra space.)
<snip>
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Ben Bacarisse
> Andrew Tomazos said:
>
>> In follow-up to these two threads:
>>
> <http://groups.google.com/group/comp.programming/browse_thread/thread/
>> f7212303f3789b37>
>> <http://groups.google.com/group/comp.lang.c/browse_thread/thread/
>> 58b60dda280aaccf>
>>
>> Here is my C implementation of an O(N) time, O(1) space solution
>> to the "one algorithm problem" of sorting an unordered array of N
>> records (A[]) that have unique integer keys in the range 0..(N-1),
>> according to an array of integers (B[]) that are a permutation of
>> the keys of A.
>>
>> I would appreciate it if someone could verify that it is correct
>> and indeed runs in O(N) time.
>
> Unfortunately, you missed an important condition of the original
> specification, to wit: "WITHOUT using any extra variable space".
I think you miss-understand what the OP meant by "variable" space.
The OP was writing in a foreign language and struggling to say "space
that depends on the problem size". Of course, even this is not exact
enough for a formal analysis (I am sure you remember the Great In
Place Merge Debate a while back) but, informally, in-place means with
only O(1) extra counters and indexes etc.
--
Ben.
Richard Heathfield
> Richard Heathfield <r...@see.sig.invalid> writes:
>
<snip>
>>
>> Unfortunately, you missed an important condition of the original
>> specification, to wit: "WITHOUT using any extra variable space".
>
> I think you miss-understand what the OP meant by "variable" space.
I hope so, for his sake! :-)
> The OP was writing in a foreign language and struggling to say
> "space that depends on the problem size".
It's entirely possible (and, if you're correct, entirely
understandable too).
mohangupta13
> Ben Bacarisse said:
>
>
>
> > Richard Heathfield <r...@see.sig.invalid> writes:
>
> <snip>
>
> >> Unfortunately, you missed an important condition of the original
> >> specification, to wit: "WITHOUT using any extra variable space".
>
> > I think you miss-understand what the OP meant by "variable" space.
>
> I hope so, for his sake! :-)
>
> > The OP was writing in a foreign language and struggling to say
> > "space that depends on the problem size".
>
depends on the problem size ".
people.
Andrew Tomazos
> > int i, j, a0, b0;
>
> This surely counts as extra space.
>
> (And no, I don't see how to do it /without/ extra space.)
Hehe. What's 16 bytes between friends? And you are forgetting about
the parameters of the function, they take up space on the stack.
The OP means in "constant space" or in "O(1) space".
The point of O(1) is even if N = 1000000, the function still uses just
16 bytes.
If you really couldn't use *any* space where are you planning on
storing the code for the algorithm? :) I suppose you could XOR it
somehow onto the A array, and then JMP A. :)
-Andrew.
blargg
[...]
> The OP means in "constant space" or in "O(1) space".
>
> The point of O(1) is even if N = 1000000, the function still uses just
> 16 bytes.
>
> If you really couldn't use *any* space where are you planning on
> storing the code for the algorithm? :) I suppose you could XOR it
> somehow onto the A array, and then JMP A. :)
Even if you ignore the code, the processor registers are space, otherwise
you're not counting something like 3072 or so bits of space on a modern
RISC processor.
Paul E. Black
keys). It appears to use A[0] as temporary storage for swaps and
such, but a single variable of type struct V should suffice.
On Monday 20 April 2009 04:28, Andrew Tomazos wrote:
> Here is my C implementation of an O(N) time, O(1) space solution to
> the "one algorithm problem" of sorting an unordered array of N records
> (A[]) that have unique integer keys in the range 0..(N-1), according
> to an array of integers (B[]) that are a permutation of the keys of A.
>
> I would appreciate it if someone could verify that it is correct and
> indeed runs in O(N) time.
>
> void assert(int b) { if (!b) while (1) /* hang */; }
>
> struct V {/* satalite data */};
>
> struct R { int key; struct V value; };
>
> void one_algo_prob(struct R* A, const int* B, const int N)
> {
> int i, j, a0, b0;
>
> for (i = 0; i < N; i++)
> if (A[i].key == 0)
> {
> A[i] = A[0];
This line overwrites the value which was in A[i] with the value in
A[0], thus loosing A[i].value forever.
> A[0].key = 0;
> break;
> }
-paul-
Below is my modification to Andrew's code. It is intended to track
the values.
// assert macro
// test assertions by compiling with -D RIGOROUS
#include <stdio.h>
#ifdef RIGOROUS
#define ASSERT(ex) {if(!(ex))(void)fprintf(stderr,"%s false in %s, line %d\n",#ex,__FILE__,__LINE__);}
#else
#define ASSERT(ex)
#endif
/*
From: Andrew Tomazos <and...@tomazos.com>
Newsgroups: comp.programming,comp.theory,comp.lang.c
Subject: Solution to "One Algorithm Problem"
Date: Mon, 20 Apr 2009 01:28:57 -0700 (PDT)
Organization: http://groups.google.com
Message-ID: <202c9dfa-72fb-4ed0...@w40g2000yqd.googlegroups.com>
In follow-up to these two threads:
<http://groups.google.com/group/comp.programming/browse_thread/thread/
f7212303f3789b37>
<http://groups.google.com/group/comp.lang.c/browse_thread/thread/
58b60dda280aaccf>
Here is my C implementation of an O(N) time, O(1) space solution to
the "one algorithm problem" of sorting an unordered array of N records
(A[]) that have unique integer keys in the range 0..(N-1), according
to an array of integers (B[]) that are a permutation of the keys of A.
I would appreciate it if someone could verify that it is correct and
indeed runs in O(N) time.
*/
//-PEB void assert(int b) { if (!b) while (1) /* hang */; }
#define assert(ex) ASSERT(ex) //+PEB
//-PEB struct V {/* satalite data */};
struct V {char *s;}; //+PEB
a0 = 0;
assert(a0 == b0);
(void)printf("A[%d].key is %d value.s is %s\n", i, A[i].key, A[i].value.s); //+PEB
}
}
int main(int argc, char** argv)
{
struct R A[10];
int B[10];
B[0] = 8;
B[1] = 2;
B[2] = 7;
B[3] = 1;
B[4] = 5;
B[5] = 0;
B[6] = 3;
B[7] = 9;
B[8] = 4;
B[9] = 6;
A[0].key = 5; A[0].value.s = "five";
A[1].key = 9; A[1].value.s = "nine";
A[2].key = 0; A[2].value.s = "zero";
A[3].key = 8; A[3].value.s = "eight";
A[4].key = 3; A[4].value.s = "three";
A[5].key = 4; A[5].value.s = "four";
A[6].key = 6; A[6].value.s = "six";
A[7].key = 7; A[7].value.s = "seven";
A[8].key = 1; A[8].value.s = "one";
A[9].key = 2; A[9].value.s = "two";
one_algo_prob(A,B,10);
}
/*
Regards,
Andrew.
--
Andrew Tomazos <and...@tomazos.com> <http://www.tomazos.com>
*/
Andrew Tomazos
> I don't think it is correct. It seems to overwrite one value (but not
> keys). It appears to use A[0] as temporary storage for swaps and
> such, but a single variable of type struct V should suffice.
Yes, this is intentional and part of the original problem (from the
original post). I should have restated that part. The A[i] with key
0 may be used as temporary storage, and doesn't hold any meaningful
data. With this allowance, the algorithm must also be O(1) space with
regard to the size of V. Using an extra variable of type V would make
it O(V) space, and break the requirement.
-Andrew.
Andrew Tomazos
As you can see from the output of your modifications everything is
correct except the one with key 0...
A[0].key is 8 value.s is eight
A[1].key is 2 value.s is two
A[2].key is 7 value.s is seven
A[3].key is 1 value.s is one
A[4].key is 5 value.s is five
A[5].key is 0 value.s is one <-- temporary/meaningless
A[6].key is 3 value.s is three
A[7].key is 9 value.s is nine
A[8].key is 4 value.s is four
A[9].key is 6 value.s is six
...as intended.
Regards,
Andrew.
Andrew Tomazos
duplication)
On Apr 28, 8:19 pm, "Paul E. Black" <p.bl...@acm.org> wrote:
> I don't think it is correct. It seems to overwrite one value (but not
> keys). It appears to use A[0] as temporary storage for swaps and
> such, but a single variable of type struct V should suffice.
Yes, this is intentional and part of the original problem (from the
tristan
#include <string.h>
using namespace std;
typedef struct Record
{
int key;
int value;
} Record;
void Order(Record a[], int lenA)
{
Record *endOfLink = NULL;
for (int i = 0; i < lenA; ++i)
{
int tempI = i;
endOfLink = &(a[a[tempI].key]);
while(endOfLink != &a[tempI])
{
if (endOfLink->key !=tempI)
{
endOfLink = &(a[endOfLink->key]);
}
else
{
int next = a[tempI].key;
Record temp;
temp = a[tempI];
a[tempI] = *endOfLink;
endOfLink->key = temp.key;
endOfLink->value = temp.value;
tempI = next;
}
}
}
}
int main()
{
Record recs[10];
for (int i = 0; i < 10; ++i)
{
recs[i].key = (i *123 + 1) % 10;
recs[i].value = i *123 + 1;
}
for (int i = 0; i < 10; ++i)
{
cout <<recs[i].key << "." << recs[i].value << " ";
}
cout << endl;
Order(recs, 10);
for (int i = 0; i < 10; ++i)
{
cout <<recs[i].key << "." << recs[i].value << " ";
}
cout << endl;
return 0;
}
Paul E. Black :
tristan
#include <string.h>
tempI = next;
}
}
}
}
Paul E. Black :
tristan
#include <string.h>
tempI = next;
}
}
}
}
Paul E. Black :
tristan
#include <string.h>
tempI = next;
}
}
}
}
Paul E. Black :