C++

Forum

 
c++ array negative numbers

leo2008 (147)
I am trying to solve this problem, but got wrong output.
Given an array of integers, write a function to move all the negative numbers to the left end of the array without changing the relative order of the non-negative numbers. The function should do this in place with a minimum number of operations.
Example:
int[] nums = {1, -1, 3, -2, -3, 5, 6, -7}
Output: [-1, -2, -3, -7, 1, 3, 5, 6]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
void move(vector<int>& arr){
  sort(arr.begin(),arr.end());
}
int main() {
 
    vector<int> arr = { 1, -1, 3, -2, -3, 5, 6, -7 };
      move(arr);
    for (int e : arr)
       cout<<e << " ";
    return 0;
}
Last edited on
DizzyDon (107)
You didn't even try. Unless you're retarded you must know that sorting isn't going to solve it.
And use CODE TAGS when posting code!
jonnin (11383)
if you are able to use anything and everything, I believe you can do this by simply defining a sort criteria function that says if its less than zero then its less than all positive values (and zero), then use the stable-sort on it with your custom function and it should be successful.
However I am not sure this is the least number of operations required. You may need to sit down and figure out if there is a better mousetrap. I suspect there is, as you need like 1 iteration of a sort, not the full blown thing, such that it 'pivots' on zero, stable. The subsequent iterations with other pivots would not be required. That gives you just N operations. But, the question is, how many operations does it do if you use your custom criteria, since that would be one and done after a single pass too, I believe. It may execute a bunch of do-nothing passes, which eat time and energy, though... you don't want that.

---------------
regardless, a normal sort will not solve the problem, it MUST be a stable sort, and it MUST only sort off (greater than) or (less than or equal) to zero.

here is 10 cents worth of effort. I fixed it for you, they now go left with the reverse of the condition I had. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <array>
 
using namespace std;

bool negleft(int a, int b)
{
	return(b >= 0 && a<0);
	
}

int main() 
{
  vector<int> v {0,-1,-2,-3,4,-5,6,-7,8,9,10,-11,12,-13,14,15,15,15,15,0,0};
  stable_sort(v.begin(), v.end(),negleft);
  
  for(int &i:v)
	  cout << i << endl;	  
}


output:
-1 -2 -3 -5 -7 -11 -13 0 4 6 8 9 10 12 14 15 15 15 15 0 0

I think its right, but its still on you to verify it for all the edge cases and ensure the condition is 100% correct. It still shows the idea, at least. Some of this is experience... its not clear what a stable sort is nor that it even exists in most textbooks, so while its a 2 line problem if you know the trick, the trick isn't well advertised to most beginners. So this is a little mercy for you because of that -- in the future, you need to show a better understanding of the problem and how to solve it and a solid try at it.
Last edited on
mbozzi (3925)
Try std::remove_if with reverse iterators?

Actually don't try this. I always forget that remove doesn't partition anything. It does separate the stuff that isn't removed from the stuff that is, but it will typically clobber half of it.
Last edited on
seeplus (6524)
to move all the negative numbers to the left end of the array without changing the relative order of the non-negative numbers


There is no requirement to have the result in any sort order. Thus a simple stable partitioning will suffice. Consider:

1
2
3
4
5
6
7
8
9
10
11
12
 
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

int main() {
	std::vector data {1, -1, 3, -2, -3, 5, 6, -7};

	std::ranges::stable_partition(data, [](int i) {return i < 0; });
	std::ranges::copy(data, std::ostream_iterator<int>(std::cout, " "));
	std::cout << '\n';
}


Which displays:

-1 -2 -3 -7 1 3 5 6


NB.

If you can't/don't want to use stable_partition, then consider simply:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <vector>
#include <iostream>
#include <iterator>

void partition(std::vector<int>& data) {
	std::vector<int> neg, pos;

	for (const auto& d : data)
		if (d < 0)
			neg.push_back(d);
		else
			pos.push_back(d);

	data.assign(neg.begin(), neg.end());
	data.insert(data.end(), pos.begin(), pos.end());
}

int main() {
	std::vector data {1, -1, 3, -2, -3, 5, 6, -7};

	partition(data);
	std::ranges::copy(data, std::ostream_iterator<int>(std::cout, " "));
	std::cout << '\n';
}

Last edited on
Registered users can post here. Sign in or register to post.