Подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Ножно подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием. Числа в файле расположены каждое в новой строке. Помогите найти ошибку.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
typedef long long LL;
 
LL interpolate(int x[], int start, int middle, int a) {
    int end = a;
    int i, j, k, *b;
    LL c;
    (int *) b = (int*) malloc ((end+1)*sizeof(int));
    for(i = start; i <= middle; i++) b[i] = x[i];
    for(j = end; i <= end; i++, j--) b[i] = x[j];
 
    for(c = 0, j = end, i = k = start; k <= end; k++)
        if(b[i] <= b[j])
            x[k] = b[i++];
        else {
          x[k] = b[j--];
          c = c + (middle - i + 1);
        }
        free(b);
    return c;
}
 
LL merge_sort(int x[], int start, int end) {
    int middle;
 
    if(start >= end) return 0;
    middle = (start + end) / 2;
 
    return  merge_sort(x, start, middle) +
            merge_sort(x, middle+1, end) +
            interpolate(x, start, middle, end);
}
 
int main() {
    int arr[100000], i=0;
    FILE * f;
    f = fopen("3.txt", "r");
    if (f == 0)
        {
            printf ("Error");
            _getch();
            return 0;
    }
    while (fscanf(f,"%d\n", &arr[i])!=EOF) i++;
    printf("Number of inversions are %lld \n", merge_sort(arr, 0, 100000-1));
    _getch();
    return 0;
}

Решение задачи: «Подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием»

textual
Листинг программы
int main() {
    int i, size=0;
    FILE *pfile=fopen("D:\\IntegerArray.txt","r"); 
    setlocale(LC_ALL, "ukr");
    while(!feof(pfile) && !ferror(pfile))
    {
         fscanf(pfile, "%*[^\n]%*c");
         size++;
    }
    rewind(pfile);
    int *A = (int*) malloc(size*sizeof(int));  
      
    for(i = 0; i < size; i++) fscanf(pfile, "%d\n", &A[i]);
    fclose(pfile);
 
    printf("Number of inversions are %lld \n", merge_sort(A, 0, size-1));
    free(A);
    _getch();
    return 0;
}

Объяснение кода листинга программы

  1. Открывается файл D:\\IntegerArray.txt для чтения.
  2. Устанавливается локальная настройка для Ukrainian языка.
  3. В цикле, пока не достигнут конец файла и нет ошибок чтения, считывается количество элементов массива.
  4. Считанные элементы сохраняются в массиве A.
  5. Вызывается функция merge_sort для сортировки массива A.
  6. Выводится количество инверсий в массиве.
  7. Массив A освобождается от выделенной памяти.
  8. Ожидается нажатие клавиши для завершения работы программы.
  9. Возвращается 0, чтобы указать, что программа успешно завершилась.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.909 из 5
Похожие ответы