#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>
/*
is_partitioned: Check whether an array is partitioned according to a predicate.
Definition:
All elements for which pred(x) == true must appear BEFORE
all elements for which pred(x) == false.
Example:
Predicate: is_even
Array: [2, 4, 6, 1, 3, 5]
Result: true (all evens come before all odds)
Array: [2, 1, 4, 3]
Result: false (4 is even but appears after an odd)
Parameters:
arr - pointer to the first element of the array
n - number of elements
pred - predicate function taking int and returning bool
Algorithm:
- Scan until the first element that does NOT satisfy the predicate.
- From that point on, ALL remaining elements must also NOT satisfy it.
- If any later element satisfies the predicate, the partition is broken.
Efficiency:
- Single pass, O(n)
- Early exit on violation
*/
bool is_partitioned(const int *arr, size_t n, bool (*pred)(int)) {
size_t i = 0;
/* Step 1: Skip all elements that satisfy the predicate */
while (i < n && pred(arr[i])) {
++i;
}
/* Step 2: Now all remaining elements must NOT satisfy the predicate */
for (; i < n; ++i) {
if (pred(arr[i])) {
return false; // Found a satisfying element after the partition boundary
}
}
return true; // Partition is valid
}
/* Predicate: check if a number is even */
bool is_even(int x) {
return (x % 2) == 0;
}
int main(void) {
int data1[] = { 2, 4, 6, 1, 3, 5 }; // properly partitioned
int data2[] = { 2, 1, 4, 3 }; // not partitioned
int data3[] = { 1, 3, 5, 7 }; // no evens, still partitioned
int data4[] = { 2, 4, 6 }; // all evens, partitioned
size_t size1 = sizeof(data1) / sizeof(data1[0]);
size_t size2 = sizeof(data2) / sizeof(data2[0]);
size_t size3 = sizeof(data3) / sizeof(data3[0]);
size_t size4 = sizeof(data4) / sizeof(data4[0]);
printf("data1 partitioned? %s\n", is_partitioned(data1, size1, is_even) ? "true" : "false");
printf("data2 partitioned? %s\n", is_partitioned(data2, size2, is_even) ? "true" : "false");
printf("data3 partitioned? %s\n", is_partitioned(data3, size3, is_even) ? "true" : "false");
printf("data4 partitioned? %s\n", is_partitioned(data4, size4, is_even) ? "true" : "false");
return 0;
}
/*
run:
data1 partitioned? true
data2 partitioned? false
data3 partitioned? true
data4 partitioned? true
*/
