This doesnt look like an in-place algo. Is O(n) possible with in-place?

Siddharth Taneja
"Karthik Kumar" <kaykaydreamz_nospamplz@yahoo.com> wrote in message
news:418c4e7a$1@darkstar...

Siddharth Taneja wrote:
The algorithm passes through the input twice. That is 2 * n,
but that is still O(n).

It uses just constant number of variables - 5 irrespective of the
number of elements in the input list. That, makes it O(1).

I was refering to the use of ur out array, the size of which is not
independent of the length of the input array.

I said O(1) would imply in-place beacuse u cant have any extra 'arrays'
which could be dependent on any of the input variables. u can use 10
variables but then only 10 for any size of input etc. And same goes for
input- ur program maybe O(n) (never denied that)...but is not in-place.
"Karthik Kumar" <kaykaylance_nospamplz@yahoo.com> wrote in message
news:418c99b9$1@darkstar...

Siddharth wrote:
) I was refering to the use of ur out array, the size of which is not
) independent of the length of the input array.
)
) I said O(1) would imply in-place beacuse u cant have any extra 'arrays'
) which could be dependent on any of the input variables. u can use 10
) variables but then only 10 for any size of input etc. And same goes for
) input- ur program maybe O(n) (never denied that)...but is not in-place.

The problem statement said 'form an array' which implies it's not in-place.
Otherwise, it would have said 'rearrange the array'.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Karthik Kumar schrieb:
The out[10] is the O(n) extra space that Siddharth refers to. If you
want to do it with stricly O(1) extra space, you have to modify the
input array.

It depends on how you interpret the wording of the original problem. I
concur with Willem that the wording is that you can use the extra output
array. However, trying to do it in-place in O(n) time is an interesting
problem in and of itself.

I can do it if any of the following conditions is true:
* every element has at least 1 duplicate
* no element has a duplicate
* there are more elements with duplicates than those without.


Michael
--
Still an attentive ear he lent Her speech hath caused this pain
But could not fathom what she meant Easier I count it to explain
She was not deep, nor eloquent. The jargon of the howling main
-- from Lewis Carroll: The Three Usenet Trolls

Siddharth Taneja wrote:
Yes. I finally found out how. See below.


Doing it in-place, assuming positive signed integers:

1 1 1 2 2 3 9 9 9 10

Step A:
Scan the array, keep singletons, but remove the first value of each run
of multiple values, and tag the first one each by inverting it.

-1 1 -2 3 -9 9 10 / ? ? ?

Step B:
Observe we have at the end one free spot for each multiple value. In a
second scan of the array, count duplicates and put the counts on the
corresponding spots.

-1 1 -2 3 -9 9 10 / 2 1 2

Step C:
Compress the first part of the array to singletons, keeping the
inversions.

-1 -2 3 -9 10 / ? ? / 2 1 2

Step D:
Put the duplicates in place, eating up the duplicate counts. We know how
many duplicates we need by the counts at the back, and we know which
ones are duplicated by the minus signs (and the order of elements) of
the singletons in front.

-1 -2 3 -9 10 / 1 1 2 9 9

Step E:
Reverse the inversions.

1 2 3 9 10 / 1 1 2 9 9

Done!


These are 5 passes with no more than N operations each, so the running
time is O(N), and there's been no extra storage used except for 3
pointers, which is O(1).



Notes:
* For efficiency, steps B and C can be combined into a single pass;
likewise steps D and E.

* If we have negative integers to sort, we need to remember where the
sign changes if there is no zero value. We need another variable for
this.

* If we have unsigned int, we can just use the MSBit, again using a
variable to keep track of where the MSBit changes from 0 to 1.

By this trick we have basically extracted storage for a single-bit
bitmap of O(n) from the storage we had; this works because we can
"compress" the MSBit into a single number when the values are in
sequential order.

If the numbers are stored string-like, this workaround may not be
possible.


Cheers
Michael
--
Still an attentive ear he lent Her speech hath caused this pain
But could not fathom what she meant Easier I count it to explain
She was not deep, nor eloquent. The jargon of the howling main
-- from Lewis Carroll: The Three Usenet Trolls

Seems good to me...good one!

Siddharth
"Michael Mendelsohn" <keine.Werbung.1300@msgid.michael.mendelsohn.de> wrote
in message news:418D33F2.1D2287E2@msgid.michael.mendelsohn.de ...

Michael Mendelsohn <keine.Werbung.1300@msgid.michael.mendelsohn.de> writes:

Requires O(n) additional space, that is, one unused bit per value
in the array.
--
Ben Pfaff
email: blp@cs.stanford.edu
web: http://benpfaff.org

/*
Michael Mendelsohn wrote:
I think the following may cover it:
*/

#include <stdio.h>

#define SZ 10
#define EMPTY 0

void printarray(int *aa, int size, char id, int ix)
{
int i;

printf("%c:", id);
for (i = 0; i < size; i++) {
printf("%3d ", aa[i]);
}
printf(" :%c:%d\n", id, ix);
} /* printarray */

/* ----------------- */

int main(void)
{
int ya[SZ];
int xa[SZ] = {1, 1, 1, 2, 2, 3, 9, 9, 9, 10};
int xp, yp;

xp = yp = 0;
printarray(xa, SZ, 'x', xp);

while (xp < SZ) {
ya[yp] = xa[xp];
xa[xp] = EMPTY;
xp++;
while ((xp < SZ) && (xa[xp] == ya[yp])) {
xp++;
}
yp++;
}

/* PHASE 2 */

xp = 0;
while (yp < SZ) {
if (EMPTY != xa[xp]) {
ya[yp] = xa[xp];
yp++;
xp++;
}
while (EMPTY == xa[xp]) xp++;
}
printarray(ya, SZ, 'y', yp);
return 0;
} /* puzzle - main */

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

Siddharth Taneja wrote:
I don't think it's that complicated.

/* BEGIN output new.c */

1 1 1 2 2 3 9 9 9 10
1 2 3 9 10 1 1 2 9 9

/* END output new.c */


/* BEGIN new.c */

#include <stdio.h>
#include <string.h>

void reorder(int *, size_t);

int main(void)
{
int array[] = {1, 1, 1, 2, 2, 3, 9, 9, 9, 10};
size_t nmemb = sizeof array / sizeof *array;
size_t count;

puts("/* BEGIN output new.c */\n");
for (count = 0; count != nmemb; ++count) {
printf("%2d ", array[count]);
}
putchar('\n');
reorder(array, nmemb);
for (count = 0; count != nmemb; ++count) {
printf("%2d ", array[count]);
}
puts("\n\n/* END output new.c */");
return 0;
}

void reorder(int *array, size_t nmemb)
{
int *pointer, *last, *done, temp;

done = array;
last = array + nmemb - 1;
while (done != last) {
pointer = done++;
while (pointer++ != last) {
if (*pointer > done[-1]) {
temp = *pointer;
memmove(done + 1, done,
(pointer - done) * sizeof *done);
*done = temp;
break;
}
if (pointer == last) {
done = last;
}
}
}
}

/* END new.c */

--
pete

Wouldn't your memove functoin be actually O(n) at times. That would make the
algorithm O(n^2)
"pete" <pfiland@mindspring.com> wrote in message
news:418D8723.61EF@mindspring.com...

pete wrote:
Agreed that it is in-place.

But with a memmove statement for every while loop,
I find it hard to believe it to be of O(n)
complexity ( as required by the *op* ).



--
Karthik. http://akktech.blogspot.com .
'Remove _nospamplz from the address to get the real one.'

Ya I guess Ben is right. This would only work for +ve integers. Michael, do
you think you have something that also works for -ve integers and does not
violate the constraints?
"Ben Pfaff" <blp@cs.stanford.edu> wrote in message
news:87y8hetnz7.fsf@benpfaff.org...

On Sat, 6 Nov 2004, Ben Pfaff wrote:
Not true of the algorithm in general; read the rest of Michael's
post. You only need (lg N) bits in order to keep track of where the
MSB switches from 0 to 1 in the original array, and then you can
use that bit as your storage space. If the OP really expected O(1)
storage, he'd have to give up on any algorithm involving indices or
pointers, and that would really be tricky... or at least require a
more specific problem statement.

HTH,
-Arthur

CBFalconer wrote:
Hmm !! This does not seem to be an
in-place algorithm .

[code snipped] .

I am not sure, if it is possible to
do an in-place - O(n) rearranging algorithm,
with arrays, since it would invariably
require shifting/moving elements from one
place to another, and that process cannot be
O(n) .

With lists, yes - we can change the pointers
and it should be possible.

--
Karthik. http://akktech.blogspot.com .
'Remove _nospamplz from the address to get the real one.'

Siddharth Taneja wrote:
At times, but I don't know how it would be on average.

In the given example of 10 elements,
the memmove function is only called 4 times.
The values of (pointer - done) in each memmove call are
2, 3, 3, and 5.

The total work done by memmove in this case,
is proportional to 13 integer assignments.

--
pete

"Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> writes:

Well, that's clever, but not O(1) as the OP requested.

I don't see how usage of indices or pointers necessarily requires
an algorithm not to use O(1) space. O(1) just means that the
requirement, for any instantiation of the algorithm on real data,
is not greater than a fixed amount. It doesn't mean that you
can't use a large (but fixed) number of variables.
--
"I've given vodka years and years of oral pleasure, and it's done the
same for me. And neither of us has really taken any steps to take the
relationship to the `next level.'"
--Jeremy Hunt

Karthik Kumar wrote:
Give me a shift register and a couple of hardware mechanisms, and I
can do it in O(N). Basically I need a comparator (< = >) and a 2:1
selector. The only analog I know of for a shift register is a
circular buffer and two pointers.

--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

CBFalconer wrote:
Well - what you are talking about is essentially about the
hardware support. But then as far as the algorithm goes, with
respect to arrays, it is impossible to achieve one with O(n) complexity
and it being in-place, since this algorithm involves rearranging the
elements.


Yeah - Agreed. Then the problem breaks down to having the data
in a list. (as a simulation of circular buffer). Then we can do it
in-place , in O(n) for sure.

--
Karthik. http://akktech.blogspot.com .
'Remove _nospamplz from the address to get the real one.'

pete <pfiland@mindspring.com> writes:

The 'reorder()' function is worst case O(n**2).
Consider an input array

a[] = { 0,0, 1,1, 2,2, 3,3, 4,4, 5,5, ... n,n, };

How many words are moved as a function of n?