#include <stdio.h>
#include <stdlib.h>
/*
Find the N smallest values in a 2D array.
Approach:
1. Flatten the 2D array into a single dynamic array.
2. Use a lightweight partition step to ensure the smallest N values
occupy the first N positions (in any order).
3. Sort only those N values for clean output.
This avoids sorting the entire dataset and is efficient for large inputs.
*/
// Comparison function for qsort
static int cmp_int(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y);
}
// Flatten a 2D array into a 1D array
static int *flatten(const int *matrix, int rows, int cols) {
int total = rows * cols;
int *flat = malloc(total * sizeof(int));
if (!flat) {
fprintf(stderr, "Allocation failed\n");
exit(EXIT_FAILURE);
}
for (int i = 0; i < total; i++) {
flat[i] = matrix[i];
}
return flat;
}
/*
Partition the array so that the smallest N elements are in the first N slots.
This is a simplified selection algorithm:
- Sort the entire array only if N is large.
- Otherwise, perform a partial selection scan.
*/
static void partial_select(int *arr, int total, int N) {
if (N >= total) return;
// Simple selection of N smallest values
for (int i = 0; i < N; i++) {
int min_index = i;
for (int j = i + 1; j < total; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// Swap smallest found into position i
int tmp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = tmp;
}
}
// Extract N smallest values
static int *smallestN(const int *matrix, int rows, int cols, int N) {
int total = rows * cols;
int *flat = flatten(matrix, rows, cols);
if (N >= total) {
qsort(flat, total, sizeof(int), cmp_int);
return flat;
}
// Partition so that first N elements are the smallest
partial_select(flat, total, N);
// Sort only the smallest N elements
qsort(flat, N, sizeof(int), cmp_int);
return flat;
}
int main(void) {
int matrix[] = {
12, 5, 7,
3, 19, 1,
8, 4, 6
};
int rows = 3;
int cols = 3;
int N = 5;
int *values = smallestN(matrix, rows, cols, N);
printf("The %d smallest values:\n", N);
for (int i = 0; i < N; i++) {
printf("%d ", values[i]);
}
free(values);
return 0;
}
/*
run:
The 5 smallest values:
1 3 4 5 6
*/
