C ++の偶数と奇数の位置での正の要素（相対的な順序は維持されません）

この問題では、配列が与えられ、すべての正の数が偶数のインデックスの場所にあり、すべての負の数が奇数のインデックスの場所にあるように配列を変換することがタスクです。

正の値と負の値の数が等しくない可能性があります。この場合、余分な値は移動しません。

問題を理解するために例を見てみましょう

入力 − {3、5、-1、19、-7、-2}

出力 − {3、-1、5、-7、19、-2}

この問題を解決するには、配列内で順序が正しくない要素を見つける必要があります。これを見つける方法は複数ある可能性があります。ここでは、そのうちの2つについて説明します。

方法1

このメソッドは、単純に配列をトラバースし、その場所にない要素の最初の出現を見つけて（つまり、正ではなく、負ではなく）、それらを交換します。アレイ全体がトラバースされるまで、このプロセスを実行します。

例

ソリューションの実装を示すプログラム

#include<iostream>
using namespace std;
void swapElements(int* a, int i , int j){
   int temp = a[i];
   a[i] = a[j];
   a[j] = temp;
   return ;
}
void printArray(int* a, int n){
   for(int i = 0; i<n; i++)
   cout<<a[i]<<"\t";
   cout<<endl;
   return ;
}
void generateOrderedArray(int arr[], int n){
   for(int i = 0; i <n; i++){
      if(arr[i] >= 0 && i % 2 == 1){
         for(int j = i + 1; j <n; j++){
            if(arr[j] < 0 && j % 2 == 0){
               swapElements(arr, i, j);
               break ;
            }
         }
      }
      else if(arr[i] < 0 && i % 2 == 0){
         for(int j = i + 1; j <n; j++){
            if(arr[j] >= 0 && j % 2 == 1){
               swapElements(arr, i, j);
               break;
            }
         }
      }
   }
   printArray(arr, n);
}
int main(){
   int arr[] = { 1, -3, 5, 6, -3, 6, 7, -4, 9, 10 };
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"Inital Array is : ";
   printArray(arr, n);
   cout<<"Array with positive numbers at even index and negative numbers at odd index :";
   generateOrderedArray(arr,n);
   return 0;
}

出力

Inital Array is : 3 5 -1 19 -7 -2
Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2

方法2

この方法では、クイックソートの手法のように見えるプロセスを使用します。ここでは、正の数と負の数の2つのポインターを使用します。正のポインターをインデックス0（偶数インデックス）に設定し、負のポインターをインデックス1（奇数インデックス）に設定します。そして、ポインターを2つ進めます。そして、正のポインターが負の数に遭遇し、負のポインターが正の数に遭遇したときに停止します。そして、両方が停止したら交換します。いずれかのポインタが配列インデックスから外れると、実行が停止します。

例

ソリューションの実装を示すプログラム

#include <iostream>
using namespace std;
void swapElements(int* a, int i , int j){
   int temp = a[i];
   a[i] = a[j];
   a[j] = temp;
   return ;
}
void printArray(int *a, int n){
   for (int i = 0; i <n; i++)
   cout<<a[i]<<"\t";
   cout<<endl;
}
void generateOrderedArray(int a[], int size){
   int positive = 0, negative = 1;
   while (1) {
      while (positive < size && a[positive] >= 0)
      positive += 2;
      while (negative <size && a[negative] <= 0)
      negative += 2;
      if (positive < size && negative < size)
         swapElements(a, positive, negative);
      else
         break;
   }
}
int main(){
   int arr[] = { 3, 5, -1, 19, -7, -2 };
   int n = (sizeof(arr) / sizeof(arr[0]));
   cout<<"Inital Array is : ";
   printArray(arr, n);
   cout<<"Array with positive numbers at even index and negative numbers at odd index : ";
   generateOrderedArray(arr, n);
   printArray(arr, n);
   return 0;
}

出力

Inital Array is : 3 5 -1 19 -7 -2
Array with positive numbers at even index and negative numbers at odd index : 3 -1 5 -7 19 -2