Back
Close

Inplace Partition Implementation

Anonymous
1,353 views
#include <stdio.h>
#include <algorithm>
using std::rotate;
bool predicate(int i)
{
return i > 0;
}
int inplace_stable_partition(int *a, int i, int n)
{
if (i == n - 1)
return predicate(a[i]) ? i + 1 : i;
int middle = i + (n - i) / 2;
i = inplace_stable_partition(a, i, middle);
n = inplace_stable_partition(a, middle, n);
rotate(a + i, a + middle, a + n);
return i + n - middle;
}
int main(int argc, char *argv[])
{
int a[] = { 1, -1, 2, -2, 3, -3 };
inplace_stable_partition(a, 0, 6);
for (int i = 0; i < 6; i++)
printf("%d ", a[i]);
return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants