Arrays: Move all the negative number in beginning

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
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *