Which solution is optimal?

Question

I have two solutions for this problem, but which is one is optimal?

A list of N numbers is given. The player has to arrange the numbers so that all the odd numbers of the list come after the even numbers. Write an algorithm to arrange the given list such that all the odd numbers of the list come after the even numbers.

Input

The first line of the input consists of an integer numbers, representing the size of the list(N). The second line of the input consists of N space-separated integers representing the values of the list

Output

Print N space-separated integers such that all the odd numbers of the list come after the even numbers

Example

Sample Input

8
10 98 3 33 12 22 21 11

Sample Output

10 98 12 22 3 33 21 11

Solution no1-

    #include<bits/stdc++.h>
using namespace std;

int main(){
    
    int n;
    cin>>n;
    
    int a[n];
    
    for(int i=0; i<n; i++)
      cin>>a[i];
      
    
    int p1=0, p2= n-1;
    
    while(p1 < p2){
        
        while(a[p1]%2 == 0 and p1<p2)
           p1++;
        
        while(a[p2]%2 != 0 and p1<p2)    
           p2--;
        
        if(p1 < p2){
            swap(a[p1], a[p2]);
            p1++;
            p2--;
        }
    }
    
    
    for(int i=0; i<n; i++)
     cout<<a[i]<<" ";
    
    return 0;
}

---

solution 2-

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int arr[n];

    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    for(int i=0;i<n;i++){
        if(arr[i]%2==0)
        cout<<arr[i]<<" ";
    }
    for(int i=0;i<n;i++){
        if(arr[i]%2!=0)
        cout<<arr[i]<<" ";
    }
    

    return 0;
}

Answer 1

I would make a few changes, but mostly follow the second example.

First, I would put in an if-statement to ensure that n is a positive number. That's just a good check to do.

Next, I wouldn't output them quite like this. I'd build a second array instead.

int inputArray[n];
int finalArray[n];
int outputIndex = 0;

... Fill inputArray like you currently fill array

for (int i = 0; i < n; ++i) {
    if (inputArray[i] % 2 == 0) {
        outputArray[outputIndex++] = inputArray[i];
    }
}

Do the second loop the same way. Then dump the outputArray.

Now, some other notes. These are stylistic, but will help you. Please use more whitespace in your code. Notice my code has spaces between operators. You're clearly young with young eyes, but good habits now will matter when you have to share code with old farts. Your scrunched-together code is really quite difficult to read and can readily hide errors. You wouldn't believe how many bugs are in code because some programmer was afraid of spaces.

Second, many programmers will tell you that optional braces shouldn't be treated as optional. Notice my if-statement has a pair of braces whereas yours don't. And if you look at how your code was formatted, you'll see that your indentation is wrong. You didn't indent your cout lines properly. This is a way errors hide. If you always use braces, evne when the language thinks they're optional, you'll have fewer bugs.

Lastly, most people will suggest you stop using fixed-length arrays and instead use vector, but as you're a new programmer, maybe you're not ready for that.

Answer 2

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int* arr = new int[n];
    int* odd = new int[n];
    int* even = new int[n];
    int oddIndex = 0;
    int evenIndex = 0;

    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    for(int i=0;i<n;i++){
        if(arr[i]%2==0)
            even[evenIndex++] = arr[i];
        else
            odd[oddIndex++] = arr[i];
    }

    for(int i=0;i<evenIndex;i++){
        cout<<even[i]<<" ";
    }

    for(int i=0;i<oddIndex;i++){
        cout<<odd[i]<<" ";
    }
    

    return 0;
}