Partition a Array

Question

Given a randomly ordered array (arr) of n elements, function partitionArray(int arr[], int n, int x) partition the elements into two subsets such that elements <= x are in left subset and elements > x are in the right subset.

The first line of the test case will contain two numbers n (number of elements in a list ) and x (number to use for partition) separated by space. The next line will contain N space-separated integers.

I am getting the wrong output for certain cases from the following Function.

Here's my code:

void partitionArray(int arr[], int n, int x)
{
    int i, j, temp;
    i = 0;
    j = n-1;
  
    while (i < j)
    {
        while (arr[i] <=x)
            i++;
        while (arr[j] > x)
            j--;
    
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    
        i++;
        j--;
    }  
}

For the cases I am getting the right output is:

10 6
28 26 25 5 6 7 24 29 6 10

For the cases I am not getting the right output is:

10 17
28 26 25 11 16 12 24 29 6 10

The output I am getting in this:

10
6
12
11
25
16
24
29
26
28

Expected Output:

10
6
12
11
16
25
24
29
26
28

10 6
28 26 25 11 5 7 24 29 6 10

The output I am getting in this:

6
25
5
11
26
7
24
29
28
10

Expected Output:

6
5
25
11
26
7
24
29
28
10

Can Anyone help me this

Answer 1

Below change will do:

if(i < j){
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

When swapping when the value of j is i+1 and arr[i]<x and arr[j]>x, after i++ and j-- from while loops, the value of j is i-1 in your code. Hence checking i<j before swapping is important.

Suppose input is

2 5
1 10

Your output will be

10 1

And the index has to be checked as index may run out of the size of the array.

while (i<n && arr[i]<=x)
    i++;
while (j>=0 && arr[j]>x)
    j--;

Example inputs:

5 7
5 3 2 4 1

5 3
7 6 9 5 6