Подсчитать количество инверсий в файле, модифицировав алгоритм сортировки слиянием - 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, чтобы указать, что программа успешно завершилась.