Problem
Give you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.
o(n)time complexity and o(1) space complexity is perfect.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Sort this array in a special way, the relative position should not be changed.
Created Date : 25-August-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
void Sort(vector<int>& vec)
{
vector<int> t0, t1;
for(auto i : vec){
i > 0 ? t1.push_back(i) : t0.push_back(i);
}
vec.swap(t0);
vec.insert(vec.end(), t1.begin(), t1.end());
}
void DoTest(vector<int>& vec)
{
cout << "Before sorting" << endl;
for(auto i: vec){
cout << setw(4) << i << " ";
}
cout << endl;
Sort(vec);
cout << "After sorting" << endl;
for(auto i: vec){
cout << setw(4) << i << " ";
}
cout << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {-1, 1, 3, -2, 2};
vector<int> vec(arr, arr + sizeof(arr) / sizeof(int));
DoTest(vec);
return 0;
}
Output
Before sorting
-1 1 3 -2 2
After sorting
-1 -2 3 1 2
Press any key to continue . . .