Сортировать целые из текстового файла

Question

Мне нужно отсортировать целые из файла в порядке возрастания и вывести их на стандартный вывод. Я не могу изменить структуру файла.

Текстовый файл выглядит следующим образом:

41
65
68
35
51

... (один номер в строке)

My Программа отлично работает с небольшими файлами, но я должен выбрать ее для больших файлов (например, 3 миллиона чисел), используя malloc, но не знаю точно, где и как. Я хотел бы попросить помощи в этом. (Я новичок)

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

#define BUFFER 100000

int sort(int size, int arr[])
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - i - 1; j++)
        {
            if (arr[j] > arr[j + 1]) 
            {
                int swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    char *filename = argv[1];

    char s[20];

    if (argc == 1)
    {
        fprintf(stderr, "Error! Input then name of a .txt file\n");
        exit(1);
    }

    FILE *fp = fopen(filename, "r");

    if (fp == NULL)
    {
        fprintf(stderr, "Error! Can't open %s\n", filename);
        exit(1);
    }
    int arr[BUFFER];

    int i = 0;
    int size = 0;

    while ((fgets(s, BUFFER, fp)) != NULL)
    {

        s[strlen(s) - 1] = '\0';

        arr[i] = atoi(s);
        ++i;
        ++size;
    }
    fclose(fp);
    sort(size, arr);

    for (int i = 0; i < size; ++i)
    {
        printf("%d\n", arr[i]);
    }

    return 0;
}

Answer 1

Чтобы прочитать неопределенное количество записей из входного файла, вы можете выделить и перераспределить массив, используя realloc(), когда читается больше записей. Для повышения производительности рекомендуется увеличивать выделенный размер кратно, а не линейно, особенно по одной записи за раз.

Ваша процедура сортировки не подходит для больших массивов: сортировка вставки имеет квадратичную c сложность по времени Таким образом, это может занять много времени для 3 миллионов элементов, если они уже не отсортированы. Для этого используйте qsort() с простой функцией сравнения.

Вот модифицированная программа:

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

static int compare_int(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    // return -1 if a < b, 0 if a == b and +1 if a > b
    return (a > b) - (a < b);
}

int main(int argc, char *argv[]) {
    if (argc == 1) {
        fprintf(stderr, "Error! Input then name of a .txt file\n");
        exit(1);
    }

    char *filename = argv[1];
    FILE *fp = fopen(filename, "r");
    if (fp == NULL) {
        fprintf(stderr, "Error! Can't open %s\n", filename);
        exit(1);
    }

    char buf[80];
    size_t n = 0, size = 0;
    int *array = NULL;

    /* read the numbers */
    while (fgets(buf, sizeof buf, fp)) {
        if (n == size) {
            /* increase size by at least 1.625 */
            size_t newsize = size + size / 2 + size / 8 + 32;
            int *newarray = realloc(array, newsize * sizeof(*array));
            if (newarray == NULL) {
                printf("cannot allocate space for %zu numbers\n", newsize);
                free(array);
                fclose(fp);
                exit(1);
            }
            array = newarray;
            size = newsize;
        }
        array[n++] = strtol(buf, NULL, 10);
    }
    fclose(fp);

    /* sort the array */
    qsort(array, n, sizeof(*array), compare_int);

    for (size_t i = 0; i < n; i++) {
       printf("%d\n", array[i]);
    }
    free(array);
    return 0;
}

Answer 2

Ваша программа может выглядеть так:

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

static int numcompar(const void *a, const void *b) {
    const int *x = a;
    const int *y = b;
    // it is tempting to return *x - *y; but undefined behavior lurks
    return *x < *y ? -1 : *x == *y ? 0 : 1;
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
         // TODO: handle error
         abort();
    }
    char *filename = argv[1];
    // open the file
    FILE *fp = fopen(filename, "r");
    if (fp == NULL) {
        abort();
    }

    // this will be our array
    // note realloc(NULL is equal to malloc()
    int *arr = NULL;
    size_t arrcnt = 0;

    // note - I am using fscanf for simplicity
    int temp = 0;
    while (fscanf(fp, "%d", &temp) == 1) {
        // note - reallocating the space each number for the next number
        void *tmp = realloc(arr, sizeof(*arr) * (arrcnt + 1));
        if (tmp == NULL) {
            free(arr);
            fclose(fp);
            abort();
        }
        arr = tmp;
        // finally assignment
        arr[arrcnt] = temp;
        arrcnt++;
    }

    fclose(fp);

    // writing sorting algorithms is boring
    qsort(arr, arrcnt, sizeof(*arr), numcompar);

    for (size_t i = 0; i < arrcnt; ++i) {
       printf("%d\n", arr[i]);
    }

    free(arr);
}

Обратите внимание, что перераспределение для одного int за раз неэффективно - realloc обычно является дорогостоящей функцией. Следующим шагом будет сохранение номера размера массива и «используемых» (назначенных) элементов массива отдельно и перераспределение массива с соотношением, превышающим 1. Есть голоса, которые предпочитают использовать число золотого сечения в таких случаях.