Segregation of negative and positive numbers in an array without using extra space, and maintaining insertion order and in O(n^2) time complexity.
Examples:
Input :9
12 11 -13 -5 6 -7 5 -3 -6
Output :-13 -5 -7 -3 -6 12 11 6 5
Input :5
11 -13 6 -7 5
Output :-13 -7 11 6 5
We have discussed this problem below posts.
- ers-beginning-positive-end-constant-extra-space/”>Rearrange positive and negative numbers without maintaining order.
- Rearrange positive and negative numbers with constant extra space
This post discusses a new approach that takes O(1) extra space. We first count total negative numbers, then move negative numbers one by one to the correct position.
Implementation:
C++
// C++ program to move all negative numbers// to beginning and positive numbers to end// keeping order.#include <iostream>using namespace std;void segregate(int arr[], int n){ // Count negative numbers int count_negative = 0; for (int i = 0; i < n; i++) if (arr[i] < 0) count_negative++; // Run a loop until all negative // numbers are moved to the beginning int i = 0, j = i + 1; while (i != count_negative) { // If number is negative, update // position of next positive number. if (arr[i] < 0) { i++; j = i + 1; } // If number is positive, move it to // index j and increment j. else if (arr[i] > 0 && j < n) { swap(arr[i], arr[j]); j++; } }}int main(){ int count_negative = 0; int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int n = sizeof(arr) / sizeof(arr[0]); segregate(arr, n); for (int i = 0; i < n; i++) cout << arr[i] << " "; } |
Java
// Java program to move all // negative numbers to beginning // and positive numbers to end// keeping order.class GFG{static void segregate(int arr[], int n){ // Count negative numbersint count_negative = 0;for (int i = 0; i < n; i++) if (arr[i] < 0) count_negative++; // Run a loop until all // negative numbers are // moved to the beginningint i = 0, j = i + 1;while (i != count_negative){ // If number is negative, // update position of next // positive number. if (arr[i] < 0) { i++; j = i + 1; } // If number is positive, move // it to index j and increment j. else if (arr[i] > 0 && j < n) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; j++; }}}// Driver codepublic static void main(String[] args) { int count_negative = 0; int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int n = arr.length; segregate(arr, n); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); }} // This code is contributed // by ChitraNayal |
C#
// C# program to move all // negative numbers to beginning// and positive numbers to end// keeping order.using System;class GFG{static void segregate(int[] arr, int n){ // Count negative numbersint count_negative = 0,i;for (i = 0; i < n; i++) if (arr[i] < 0) count_negative++; // Run a loop until all // negative numbers are// moved to the beginningi = 0;int j = i + 1;while (i != count_negative) { // If number is negative, // update position of next // positive number. if (arr[i] < 0) { i++; j = i + 1; } // If number is positive, move // it to index j and increment j. else if (arr[i] > 0 && j < n) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; j++; }}}// Driver codepublic static void Main() { int[] arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int n = arr.Length; segregate(arr, n); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); }} // This code is contributed // by ChitraNayal |
Python 3
# Python 3 program to move all # negative numbers to beginning# and positive numbers to end# keeping order.def segregate(arr, n): # Count negative numbers count_negative = 0 for i in range(n): if (arr[i] < 0): count_negative += 1 # Run a loop until all # negative numbers are # moved to the beginning i = 0 j = i + 1 while (i != count_negative): # If number is negative, # update position of next # positive number. if (arr[i] < 0) : i += 1 j = i + 1 # If number is positive, move # it to index j and increment j. elif (arr[i] > 0 and j < n): t = arr[i] arr[i] = arr[j] arr[j] = t j += 1 # Driver Codecount_negative = 0arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6 ]segregate(arr, 9)for i in range(9): print(arr[i] , end =" ")# This code is contributed# by ChitraNayal |
PHP
<?php // PHP program to move all // negative numbers to // beginning and positive // numbers to end keeping order.function segregate(&$arr, $n){ // Count negative numbers $count_negative = 0; for ($i = 0; $i < $n; $i++) if ($arr[$i] < 0) $count_negative++; // Run a loop until all // negative numbers are // moved to the beginning $i = 0; $j = $i + 1; while ($i != $count_negative) { // If number is negative, // update position of next // positive number. if ($arr[$i] < 0) { $i++; $j = $i + 1; } // If number is positive, move // it to index j and increment j. else if ($arr[$i] > 0 && $j < $n) { $t = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $t; $j++; } }}// Driver Code$count_negative = 0;$arr = array(-12, 11, -13, -5, 6, -7, 5, -3, -6);$n = sizeof($arr);segregate($arr, $n);for ($i = 0; $i < $n; $i++) echo $arr[$i] ." "; // This code is contributed// by ChitraNayal?> |
Javascript
<script>// JavaScript program to move all negative numbers// to beginning and positive numbers to end// keeping order.function segregate(arr, n){ // Count negative numbers let count_negative = 0; for (let i = 0; i < n; i++) if (arr[i] < 0) count_negative++; // Run a loop until all negative // numbers are moved to the beginning let i = 0, j = i + 1; while (i != count_negative) { // If number is negative, update // position of next positive number. if (arr[i] < 0) { i++; j = i + 1; } // If number is positive, move it to // index j and increment j. else if (arr[i] > 0 && j < n) { let t = arr[i]; arr[i] = arr[j]; arr[j] = t; j++; } }} let count_negative = 0; let arr = [ -12, 11, -13, -5, 6, -7, 5, -3, -6 ]; let n = arr.length; segregate(arr, n); for (let i = 0; i < n; i++) document.write(arr[i] + " ");// This code is contributed by Surbhi Tyagi.</script> |
Output
-12 -13 -5 -7 -3 -6 11 6 5
Complexity Analysis:
- Time Complexity: O(n2)
- Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
