Подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием - 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; }
Объяснение кода листинга программы
- Открывается файл
D:\\IntegerArray.txt
для чтения. - Устанавливается локальная настройка для Ukrainian языка.
- В цикле, пока не достигнут конец файла и нет ошибок чтения, считывается количество элементов массива.
- Считанные элементы сохраняются в массиве
A
. - Вызывается функция merge_sort для сортировки массива
A
. - Выводится количество инверсий в массиве.
- Массив
A
освобождается от выделенной памяти. - Ожидается нажатие клавиши для завершения работы программы.
- Возвращается 0, чтобы указать, что программа успешно завершилась.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д