Question

Consider an array of length n containing positive and negative integers in random order. Write C++ code that rearranges the integers so that the negative integers appear before the positive integers. Your solution should use

1. O(n²) operations

2. O(n) operations

Answer 1

a)

#include <iostream>

using namespace std;

void printArray(int arr[], int n)

{

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

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

  cout << endl;

}

void rearrange(int arr[], int n)

{

  int key, j;

  for (int i = 1; i < n; i++) {

    key = arr[i];

    if (key > 0)

      continue;

    j = i - 1;

    while (j >= 0 && arr[j] > 0) {

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

      j = j - 1;

    }

    arr[j + 1] = key;

  }

}

int main()

{

  int arr[] = {1, -6, 11, 18, -6, -18, -9, 11, 18, -4 };

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

  rearrange(arr, n);

  printArray(arr, n);

  return 0;

}

1 #include <iostream> using namespace std; > clang++-7 -pthread -o main main.cpp ./main -6 -6 -18 -9 -4 1 11 18 11 18 4 void printArray(int arr[], int n) 6 7 for (int i = 0; i<n; i++) cout << arr[i] << " "; cout << endl; void rearrange (int arr[], int n) int key, j; for (int i = 1; i<n; i++) { key = arr[i]; if (key > 0) continue; j = i - 1; while (j >= 0 && arr[j] > 0) { arrlj + 1] = arr[j]; j = j - 1; arrij + 1] = key; int main() int arr[] = {1, -6, 11, 18, -6, -18, -9, 11, 18, -4 }; int n = sizeof(arr) / sizeof(arr[0]); rearrange arr ni

b)

#include <iostream>

using namespace std;

void rearrange(int arr[], int n)

{

  int j = 0;

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

    if (arr[i] < 0) {

      if (i != j)

        swap(arr[i], arr[j]);

      j++;

    }

  }

}

void printArray(int arr[], int n)

{

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

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

}

int main()

{

  int arr[] = {1, -6, 11, 18, -6, -18, -9, 11, 18, -4 };

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

  rearrange(arr, n);

  printArray(arr, n);

  return 0;

}

1 #include <iostream> using namespace std; ? clang++-7 -pthread -o main main.cpp > ./main -6 -6 -18 -9 -4 11 18 11 18 1 | 4 void rearrange(int arr[], int n) int j = 0; for (int i = 0; i<n; i++) { if (arr[i] < 0) { if (i != j) swap(arr[i], arr[j]); j++; 15 16 17 18 19 20 void printArray(int arr[], int n) { for (int i = 0; i<n; i++) cout << arr[i] << " "; } int main() 22 23 int arr[] = {1, -6, 11, 18, -6, -18, -9, 11, 18, -4 }; int n = sizeof(arr) / sizeof(arr[0]); rearrange(arr, n); printArray(arr, n); return 0; 27 28 30