Partition of Array by Element given X-CodePudding

I Am Trying To Find Partition Of Array ,On Condition By Checking Variable x ,when less then x they will be on one side or else on another. but my code need some correction. HERE am not able to find the error , i will be thankful to you if you help me. Code is:-

#include<iostream>
using namespace std;
int partition(int arr[],int n,int x){
    for(int i=0;i<n;){
        if(arr[i]<x){
            i  ;
        }
        else if(arr[i]==x){   
            int temp=arr[i];
            arr[i]=arr[n];
            arr[n]=temp;
            i--;
        }
        else if(arr[i]>x){
            int temp=arr[i];
            for(int j=i;j<n;j  ){
                arr[j]=arr[j 1];   
            }
            arr[n]=temp;
           i--;
        }
    } 
    return 0;
}


int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i  ){
        cin>>arr[i];    
    }
    int x;
    cin>>x;
    
    partition(arr,n,x);
    
     for(int i=0;i<n;i  ){
        cout<<arr[i]<<"\t";
     }
    return 0;
}

Input >> array={2,10,15,1,3,15} ,x=10

Expected << {2,1,3,10,15,15}

Output I get << nothing .

CodePudding user response：

The code isn't giving any output because, first, the "cin" and "cout" are in upper case which is syntactically incorrect, secondly, the variable j is in different case in loop statement and body inside the second else-if clause in the partition function, same goes for the "I" in the first for loop in the main() function. Sort this out and you should be good to go.

CodePudding user response：

First in C the size of an array must be a compile-time constant. So for example, consider the following examples:

int n = 10;
int arr[n]; //INCORRECT

The correct way to write the above would be:

const int n = 10;
int arr[n]; //CORRECT

Similarly, in your code,

int n;
cin>>n;
int arr[n]; //INCORRECT because n is not a constant expression

Second, in your code, when you wrote:

arr[n] = temp; Undefined behavior

you're going out of bounds and so you have undefined behavior.

Solution

You can use std::stable_partition and std::vector to solve your problem as shown below:


#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    int n;
    std::cout <<"Enter n:"<<std::endl;
    std::cin >> n;
    
    std::vector<int> arr(n); //create a vector of size n instead of an array 
    
    std::cout<<"Enter elements: "<<std::endl;
    //iterate and take input from user
    for(int &elem: arr){
        std::cin >> elem ;     
    }
    int x;
    std::cout << "Enter x: "<<std::endl;
    std::cin>>x;
    
    //use std::partition
    std::stable_partition(arr.begin(), arr.end(), [x](int i){return (i < x);});
    
    std::cout<<"This is the partitioned vector: "<<std::endl;
    
    for(int i=0;i<n;i  )
    {
        std::cout<<arr[i]<<"\t";
    }
    return 0;
}

Output

The output of the above program is as follows:

Enter n:
6
Enter elements: 
2
10
15
1
3
15
Enter x: 
10
This is the partitioned vector: 
2       1       3       10      15      15

which can be seen here.