Question

How to find the K smallest numbers in an unsorted array with C

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int compare_ints(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* k_smallest_numbers(const int* arr, size_t len, int k, size_t* out_len) {
    if (arr == NULL || len == 0 || k < 0) {
        fprintf(stderr, "Invalid input\n");
        *out_len = 0;
        return NULL;
    }
    if (k == 0 || k > len) {
        *out_len = 0;
        return NULL;
    }

    // Copy the input array
    int* copy = malloc(len * sizeof(int));
    if (!copy) {
        perror("malloc");
        *out_len = 0;
        return NULL;
    }
    for (size_t i = 0; i < len; ++i) {
        copy[i] = arr[i];
    }

    // Sort the copy
    qsort(copy, len, sizeof(int), compare_ints);

    // Allocate result array
    int* result = malloc(k * sizeof(int));
    if (!result) {
        perror("malloc");
        free(copy);
        *out_len = 0;
        return NULL;
    }

    for (int i = 0; i < k; ++i) {
        result[i] = copy[i];
    }

    free(copy);
    
    *out_len = k;
    
    return result;
}

int main() {
    int arr[] = {42, 29, 90, 21, 90, 88, 37, 45};
    int k = 3;
    size_t out_len = 0;

    int* result = k_smallest_numbers(arr, sizeof(arr)/sizeof(arr[0]), k, &out_len);
    if (out_len == 0) {
        puts("k > arr size");
    }
    if (result) {
        printf("[");
        for (size_t i = 0; i < out_len; ++i) {
            printf("%d", result[i]);
            if (i < out_len - 1) printf(", ");
        }
        printf("]\n");
        free(result);
    }

    return 0;
}


/*
run:

[21, 29, 37]

*/

 

70+ SQL courses for beginners and professionals