Input: arr = {1,-3,9,-5,-2,6,4,-7}

Output: {-3,-5,-2,-7,9,6,4,1} when order is not maintained.

Output: {-3,-5,-2,-7,9,6,4,1} when order is maintained.

Explanation: The input contains an unsorted array with multiple elements both positive and negative. The output is the rearrangement of the positive and negative elements in the array.

There are two approaches to solve it:

Case 1: Rearrange the array without maintaining the order.
Case 2: Rearrange the array with the order maintained.

# Rearrange the array without maintaining the order

# Algorithm

  1. Pass the given array to the function to rearrange the array elements.
  2. Iterate through the array and find the negative element in the array and replace it with the first encountered positive element.
  3. Then swap the elements and continue the process for all the negative elements.
  4. The rearranged array is displayed on the console.

Code:

#include <iostream>

using namespace std;

void rearr(int a[], int num)

{

    int i,j=0;

    for(i = 0; i < num; i++)

    {

        if(a[i] < 0)

        {

            if(i != j)

            {

                int t = a[i];

                a[i] = a[j];

                a[j] = t;

            }

            j=j+1;

        }

    }

}

int main()

{

    int n,i;

    cout << "Enter the number of elements : "<<endl;

    cin >> n;

    int array[n];

    cout << "Enter the array elements : "<<endl;

    for(i = 0; i < n; i++)

    {

        cin >> array[i];

    }

    cout << "Original array is: "<<endl;

    for(i = 0; i < n; i++)

    {

    cout << array[i] << " ";

    }

    cout << endl;

    rearr(array, n);

    cout << "Rearranged array is: "<<endl;

    for(i = 0; i < n; i++)

    {

        cout << array[i] << " ";

    }

    cout << endl;

    return 0;

}

Output:

Enter the number of elements:

8

Enter the array elements:

1

-3

9

-5

-2

6

4

-7

Original array is:

1 -3 9 -5 -2 6 4 -7

Rearranged array is:

-3 -5 -2 -7 9 6 4 1

Time Complexity: O(N)

# Rearrange the array with the order maintained

# Algorithm

  1. Pass the given array to the function to rearrange the array elements.
  2. Iterate through the array and find the negative element in the array and insert it within the array in the sequence of 0 to n-1 by shifting the positive element one position to the right.
  3. If the encountered element is positive, then skip it and move on to the next element. 
  4. The rearranged array is displayed on the console.

Code:

#include <iostream>

using namespace std;

void rearr(int a[], int num)

{

   int i,t, j;

    for(i = 1; i < num; i++)

    {

    t = a[i];

    if (t > 0)

    continue;

    j = i - 1;

    while ( a[j] > 0 && j >= 0)

    {

    a[j + 1] = a[j];

    j--;

    }

    a[j + 1] = t;

    }

}

int main()

{

    int n,i;

    cout << "Enter the number of elements : "<<endl;

    cin >> n;

    int array[n];

    cout << "Input the array elements : "<<endl;

    for(i = 0; i < n; i++)

    {

        cin >> array[i];

    }

    cout << "Original array is: "<<endl;

    for(i = 0; i < n; i++)

    {

    cout << array[i] << " ";

    }

    cout << endl;

    rearr(array, n);

    cout << "Rearranged array is: "<<endl;

    for(i = 0; i < n; i++)

    {

        cout << array[i] << " ";

    }

    cout << endl;

    return 0;

}

Output:

Enter the number of elements:

8

Enter the array elements:

1

-3

9

-5

-2

6

4

-7

Original array is:

1 -3 9 -5 -2 6 4 -7

Rearranged array is:

-3 -5 -2 -7 1 9 6 4

Time Complexity: O(N^2)

# Optimized Algorithm for Case 2

  1. Pass the given array to the function to rearrange the array elements.
  2. Iterate through the array and sort the elements using merge sort.
  3. While positioning the elements in the subarray place first the negative elements of both the right and left subarrays and then the positive elements using additional condition in the algorithm. 
  4. The rearranged array is displayed on the console.

Code:

#include <iostream> 

using namespace std; 

void modifiedmerge(int arr[], int l, int m, int r) 

{ 

    int i, j, k; 

    int l1 = m - l + 1; 

    int l2 = r - m;

    int LA[l1], RA[l2];

    for (i = 0; i < l1; i++) 

    {

        LA[i] = arr[l + i]; 

    }    

    for (j = 0; j < l2; j++) 

    {

        RA[j] = arr[m + 1 + j]; 

    }    

    i = 0; 

    j = 0; 

    k = l;  

    while (i < l1 && LA[i] < 0) 

    {

        arr[k++] = LA[i++]; 

    }    

    while (j < l2 && RA[j] < 0) 

    {

        arr[k++] = RA[j++];

    }

    while (i < l1) 

    {

        arr[k++] = LA[i++];

    }

    while (j < l2) 

    {

        arr[k++] = RA[j++]; 

    }

} 

void rearr(int arr[], int l, int r) 

{ 

    if (l < r) { 

        int mid = l + (r - l) / 2;

        rearr(arr, l, mid); 

        rearr(arr, mid + 1, r); 

        modifiedmerge(arr, l, mid, r); 

    } 

} 

int main() 

{ 

    int arr[] = { 1 ,-3 ,9 ,-5 ,-2 ,6 ,4 ,-7 }; 

    int len = sizeof(arr) / sizeof(arr[0]);

    cout<<"Original array is:"<<endl;

    for (int i = 0; i < len; i++) 

        cout << arr[i] << " "; 

    cout << endl;

    rearr(arr, 0, len - 1); 

    cout<<"Rearranged array is:"<<endl;

    for (int i = 0; i < len; i++) 

        cout << arr[i] << " "; 

    cout << endl;

    return 0; 

}

Output:

Original array is:

1 -3 9 -5 -2 6 4 -7

Rearranged array is:

-3 -5 -2 -7 1 9 6 4

Time Complexity: O(NlogN)

This way with more practices of data structures and algorithms we can approach towards efficient source codes of any particular programs.

Report Error/ Suggestion

Related Posts:

[yuzo_views]











CopyRight © 2020

CopyRight © 2020