@All *Here is the working code: test on input {-1,5,3,-8,4,-6,9} and
{1,-1,2}*
Algo:
increment current till first +ve number(p) and decerement end till last
-ve number(n)
now consider only array between [p..n]
If current is negetive, increment current
If current is positive, swap it with end and decrement end, and current
(if current < 0)
current =0;
if current >=end then breck;
now n1=first negetive no. n2= last negetive number
similarly p1=first positive number and p2 last positive number
swap array elements in between n1,n2 and p1,p2 , like first element is last
element and secound to secound last .....
JavaCode:
public class OneSideNegOtherPostive {
private int start, end, current;
public void getOrderedArray(int b[]) {
start = 0;
end = b.length - 1;
while (b[start] < 0)
start++;
while (b[end] >= 0)
end--;
int n = start, p = end;
current = n;
while (current < end) {
while (b[current] < 0 && (current < end)) {
current++;
continue;
}
ArrayUtils.swap(b, current, end);
ArrayUtils.printArray(b, " \n b at current " + current + " end "
+ end + "==>");
current--;
end--;
if (current < 0)
current = 0;
}
ArrayUtils.swapWithIn(b, n, p);
}
* public static void main(String args[]) {
OneSideNegOtherPostive oNegOtherPostive = new
OneSideNegOtherPostive();
//int a[] = { -1, 5, 3, -8, 4, -6, 9 };
int a[] = {1,-1,2};
ArrayUtils.printArray(a, "Input array ");
oNegOtherPostive.getOrderedArray(a);
ArrayUtils.printArray(a, "\nOutput array ");
}*
}
public class ArrayUtils {
public static void swap(Object a, Object b, int end) {
Object tmp = a;
a = b;
b = tmp;
}
public static void swap(int array[], int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
public static void swapWithIn(int b[], int n, int p) {
int nEnd, nStart = n, pEnd = p, pStart;
int i = 0;
while (b[i] < 0) {
i++;
}
pStart = i;
nEnd = pStart - 1;
while (nStart < nEnd) {
ArrayUtils.swap(b, nStart, nEnd);
nStart++;
nEnd--;
}
while (pStart < pEnd) {
ArrayUtils.swap(b, pStart, pEnd);
pStart++;
pEnd--;
}
}
public static void printArray(int a[], String message) {
System.out.print(message);
for (int x : a) {
System.out.print(" " + x);
}
}
}
On Sun, Jul 1, 2012 at 9:38 AM, Dave <[email protected]> wrote:
> @Navin: If I am correctly executing your algorithm on the data in the
> original posting, {-1,5,3,-8,4,-6,9}, I get {-1,-6,-8,4,3,5,9}, when the
> correct answer is {-1,-8,-6,5,3,4,9}. The array contains the correct
> numbers, but the order of the positive numbers and the order of the negtive
> numbers is not maintained. You can't swap a number from the front part of
> the array with a number from the back part and expect the order of
> positives and negatives to remain intact.
>
> Dave
>
> On Saturday, June 30, 2012 12:42:09 AM UTC-5, Navin Gupta wrote:
>
>> @Dave :- a minor change
>> Initially, decrement the end pointer till it points to positive number,
>> Now end points to the last negative number.
>> Now,
>> If current is negative , increment current
>> If current is positive , swap it with the element at end and decrement
>> current and end both
>> If current >= end , then break.
>> Algo :-
>> cur = 0;
>> end = size - 1;
>> while ( a[end] > 0 && end > 0 ) end - - ;
>> while ( cur <end ) {
>> if( a[cur] < 0 ) cur++;
>> else{
>> swap( a[cur], a[end] );
>> end - - ;
>> } // end of if-else
>> } // end of while
>> In the above example :- ( 1, -1, 2 ), current points to 1 (cur=0) and end
>> points to -1 (end =1 ) after end has been decremented.
>> Now swap the element at current and end pointers.
>> Now cur = 0, end =0, break condition is reached. the output is :- ( -1,
>> 1, 2 )
>> Please check.
>>
>> Navin Kumar Gupta
>> Final Year, B.Tech (Hons.)
>> Computer Science & Engg.
>> National Institute of Technology,Jamshedpur
>> Mob - (+91) 8285303045
>>
>> On Friday, 29 June 2012 22:28:15 UTC+5:30, Dave wrote:
>>>
>>> @Navin: Try this with {1,-1,2}. current points to the 1 and end points
>>> to the 2. Since 1 is positive, the algorithm swaps the 1 and the 2, giving
>>> {2,-1,1}. Then it decrements current to point outside the array and end to
>>> point to the -1. How can this be right?
>>>
>>> Dave
>>>
>> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/97r3CtynC8oJ.
>
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
--*
*
Regards
**
*Divesh Dixit*
*Software Developer
Webaroo Technology India Pvt Ltd,
***** *cell:* +91-773895195 | +91-8291302034
[email protected] | www.smsgupshup.com
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
