Question:
Given an unsorted array with positive and negative elements, move all the elements to the beginning of the array.
Example:
Input : {5, -6, 7, -8, 9, -10}
Output : {-8, -6, -10, 5, 9, 7}
We can solve this by many different methods. Some of the methods are discussed below:
1. By Sorting
2. By using partition process of quick sort
Method 1: By Sorting
If you sort the array, we will get the expected o/p.
Here if we use sorting algorithm as Merge Sort, Heap Sort, the time complexity will be O(N Log N)
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
using namespace std;
int main()
{
int arr[] = {5, -6, 7, -8, 9, -10};
int len = 6;
cout<<"Original array is = ";
for (int i = 0; i < len; ++i)
{
cout<<arr[i]<< " ";
}
sort(arr, arr+len);
cout<<"\nOutput array is = ";
for (int i = 0; i < len; i++)
{
cout<<arr[i]<< " ";
}
cout<<endl;
return 0;
}
Output:
Original array is = 5 -6 7 -8 9 -10
Output array is = -10 -8 -6 5 7 9
Method 2: By using partition process of quick sort
In this method, we will partition the array in to 2 parts.
First part will have -ve elements. Second part will have +ve elements.
Solution in C++
Here we will call a function, “partition”, that will separate +ve and -ve the elements.
Idea is very simple, we loop through every element of the array.
If the element is less than 0, then we swap that element and increment a counter, in our case it is “j”.
Here the time complexity will be O(n) as we need to loop through all the elements of the array.
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
using namespace std;
void partition(int arr[], int len)
{
int j = 0;
for (int i = 0; i < len; i++)
{
//check if the element is less than 0
if(arr[i] < 0)
{
//if true, swap the current element with the element at the index j
swap(arr[i], arr[j]);
//increment j
j++;
}
}
}
int main()
{
int arr[] = {5, -6, 7, -8, 9, -10};
int len = 6;
cout<<"Original array is = ";
for (int i = 0; i < len; ++i)
{
cout<<arr[i]<< " ";
}
partition(arr, len);
cout<<"\nOutput array is = ";
for (int i = 0; i < len; i++)
{
cout<<arr[i]<< " ";
}
cout<<endl;
return 0;
}
Output:
Original array is = 5 -6 7 -8 9 -10
Output array is = -6 -8 -10 5 9 7