В C у меня возникли проблемы с алгоритмом сортировки элементов из файла от наибольшего к наименьшему

Question

Я должен прочитать файл, выделить массив размера k и сохранить k самых больших чисел в массиве.Я знаю, как сканировать и читать файл и сортировать его, но я не знаю, как связать их вместе.Я буду очень рад, если кто-нибудь сможет мне помочь с этой проблемой!

Я пытался вычислить размер цикла, подсчитывая циклы fscanf, но ни один из них не помог.Часть с ???это где я не знаю, что поставить.Как правило, я бы поставил количество элементов, но в этом случае количество элементов в файле неизвестно.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
int main(int argc, char *argv[])//
{

    FILE *iFile;
    int k = atoi(argv[1]);//convert strings into int
    int i = 0, j = 0, n = 0, temp = 0;
    int *arr = (int *)malloc(k * sizeof(int));//allocate size k in an array

    iFile = fopen("a.txt", "r");

    if (iFile == NULL)
        return -1;
    while (feof(iFile) <= 0)
    {
        fscanf(iFile, "%d", arr);
        //find number of elements since I have to compare all the numbers with each other


    }
    //reverse
    for (i = 0; i < ??? - 1; i++)                     //Loop for descending ordering
    {
        for (j = 1; j <= ??? - 1; j++)             //Loop for comparing other values
        {
            if (arr[j] < arr[i])                //Comparing other array elements
            {
                temp = arr[i];         //Using temporary variable for storing last temp
                arr[i] = arr[j];            //replacing temp
                arr[j] = temp;             //storing last temp
            }
        }
    }

     for (i = 0; i < k; i++)                     //Loop for printing array 
     data after sorting
     {
printf("%d\n", arr[i]);                   //Printing data
     }

    free(arr);
    fclose(iFile);

    return 0;
}

Answer 1

Здесь предложение, так как я использую отсортированный массив, в моем случае в порядке возрастания, потому что это кажется более «естественным» (для использования в порядке убывания почти ничего не меняется).

Для сортировки 'k'первые значения, которые я использую qsort из stdlib , и функцию comp для выполнения необходимых сравнений.

Основным является функция insert , поскольку массив отсортирован, можно сначала найти, куда вставить новый элемент со сложностью log2 (k), но после этого может потребоваться переместить уже имеющиеся элементы на 1 позицию, чтобы создать местодля нового элемента, поэтому я предпочел выполнить поиск и перемещение одновременно.

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

/* for qsort */
int comp(const void * p1, const void * p2)
{
  return (*((int *) p1) - *((int *) p2));
}

/* insert v in arr having sz elts */
void insert(int * arr, int v, int sz)
{
  if (v > arr[0]) {
    /* search and move elts to let a hole for the new elt */
    for (int i = 1; i != sz; ++i) {
      if (v <= arr[i]) {
        /* place it in the hole */
        arr[i - 1] = v;
        return;
      }
      arr[i - 1] = arr[i];
    }

    /* v is the greater value */
    arr[sz - 1] = v;
  }
}

int main(int argc, char *argv[])
{
  int k;
  FILE * iFile;
  int * arr;

  if ((argc != 3) || (sscanf(argv[1], "%d", &k) != 1))
    fprintf(stderr, "Usage: %s <number of value> <file>\n", *argv);
  else if (k < 1)
    fprintf(stderr, "<number of value> must be greater than 0\n");
  else if ((iFile = fopen(argv[2], "r")) == NULL)
    fprintf(stderr, "cannot open '%s'\n", argv[2]);
  else if ((arr = malloc(k * sizeof(int))) == NULL)
    fprintf(stderr, "cannot allocate an array of %d in\n", k);
  else {
    /* read first 'k' values */
    int i;

    for (i = 0; i != k; ++i) {
      if (fscanf(iFile, "%d", &arr[i]) != 1) {
        fprintf(stderr, "invalid file or too few values in\n");
        fclose(iFile);
        return -1;
      }
    }

    /* sort them */
    qsort(arr, k, sizeof(int), comp);

    /* manage all the next values */
    int v;

    while (fscanf(iFile, "%d", &v) == 1)
      insert(arr, v, k);

    fclose(iFile);

    /* print result */
    for (i = 0; i != k; ++i)
      printf("%d ", arr[i]);
    putchar('\n');
    free(arr);
    return 0;
  }

  return -1;
}

Компиляция и выполнение:

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall k.c
pi@raspberrypi:/tmp $ cat a.txt 
12 78 6 2 9 56 3 45 21 0 1 56 0
pi@raspberrypi:/tmp $ ./a.out 10 a.txt 
2 3 6 9 12 21 45 56 56 78 
pi@raspberrypi:/tmp $ ./a.out 3 a.txt 
56 56 78 
pi@raspberrypi:/tmp $ ./a.out 1 a.txt 
78 

Выполнение в valgrind :

pi@raspberrypi:/tmp $ valgrind ./a.out 10 a.txt 
==2217== Memcheck, a memory error detector
==2217== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2217== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2217== Command: ./a.out 10 a.txt
==2217== 
2 3 6 9 12 21 45 56 56 78 
==2217== 
==2217== HEAP SUMMARY:
==2217==     in use at exit: 0 bytes in 0 blocks
==2217==   total heap usage: 4 allocs, 4 frees, 5,512 bytes allocated
==2217== 
==2217== All heap blocks were freed -- no leaks are possible
==2217== 
==2217== For counts of detected and suppressed errors, rerun with: -v
==2217== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)