7
2
From SO.
You are given an array with positive and negative integers. Write a function to change the elements order in the array such that negative integers are at the beginning, the positive integers are at the end and two integers that have the same sign don't change order.
Example:
- Input 1,7,-5,9,-12,15
- Output -5,-12,1,7,9,15
- Input 1,-2,-1,2
- Output -2, -1, 1, 2
Constraints: O(n) time limit and O(1) extra memory.
Alexandru
Posted 2011-02-04T12:05:56.357
Reputation: 5 485
@marcog: It is not a code golf, just a puzzle. – Alexandru – 2011-02-06T14:46:41.710
6It's not possible in O(1) memory unless you use a transdichotomic machine model. An index into an array of length n takes up log n space. – FUZxxl – 2015-01-30T11:33:14.900
I think that if a solution was known it would be well-known, given the implications for quicksort. – Peter Taylor – 2012-07-02T09:32:12.860
Is this even possible? :\ – st0le – 2012-07-02T09:34:00.270
@FUZxxl So are the linked SO question/answers wrong? – mbomb007 – 2016-06-29T22:00:55.033
2@mbomb007 Yes. Storing an index into an array of size O(n) takes O(log n) space. none of the linked answers account for that. – FUZxxl – 2016-06-29T22:43:58.280
@FUZxxl In that case, shouldn't the question be deleted? – mbomb007 – 2016-09-26T20:25:40.700
4I'm voting to close this question as off-topic because the challenge is not solvable. – mbomb007 – 2016-09-26T20:26:28.230
@Alexandru Deleted my answer. I've misread the specifications :) – Dr. belisarius – 2011-02-04T15:14:08.193
O(1) extra memory makes it impossible to solve in languages without mutable data structures (and unwieldy to solve in languages which default to immutable data structures) :-( – sepp2k – 2011-02-04T15:42:14.503
@sepp2k. I know, but without O(1) extra memory it is too easy. – Alexandru – 2011-02-04T15:43:34.147
2Is it at all possible in O(1) memory? The SO people haven't found one yet. – J B – 2011-02-05T05:46:17.650
1This question doesn't mention anything about being a code golf, yet the answers are all golfing. Can you clarify this? If it was intended to be code golf, this shows people are not specifying properly and that is a problem. If it was not, then answerers are not looking at the lack of the shortest code constraint and that is also a problem. – marcog – 2011-02-05T12:15:04.650
If instead of an array we could any kind of list, I can think of a solution. Using strictly an array, I can't come up with a linear solution. – Juan – 2011-02-05T21:16:04.827