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