Мой код для расчета числа инверсии в массиве. Расчет работает нормально.
Проблема в том, что обычно диапазон unsigned int равен 4 294 967 295, но он принимает только диапазон 2 147 483 647, что эквивалентно, он не распознает неподписанный тип данных, а принимает его как подписанный.
unsigned int _mergeSort(int arr[], int temp[], unsigned int left, unsigned int right);
unsigned int merge(int arr[], int temp[], unsigned int left, unsigned int mid, unsigned int right);
unsigned int mergeSort(int arr[], int array_size) {
int *temp = (int *)malloc(sizeof(int)*array_size);
return _mergeSort(arr, temp, 0, array_size - 1);
}
unsigned int _mergeSort(int arr[], int temp[], unsigned int left, unsigned int right) {
unsigned int mid;
unsigned int inv_count = 0;
if (right > left) {
mid = (right + left) / 2;
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);
inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}
unsigned int merge(int arr[], int temp[], unsigned int left, unsigned int mid, unsigned int right) {
unsigned int i, j, k;
unsigned int inv_count = 0;
i = left;
j = mid;
k = left;
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
}
while (i <= mid - 1)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
int main(int argv, char** args) {
const int size = 100000;
int arr[size];
unsigned int i = 0;
int converted;
string input;
fstream dataFile("IntegerArray.txt", ios::in);
if (dataFile) {
getline(dataFile, input);
while (dataFile) {
converted = atoi(input.c_str());
arr[i++] = converted;
getline(dataFile, input);
}
dataFile.close();
} else {
cout << "error" << endl;
}
printf("Number of inversions are %d \n", mergeSort(arr, i));
getchar();
return 0;
}
В вашем звонке printf()
вы используете спецификатор формата %d
что значит целое число со знаком. Фактическое переданное значение является целое число без знака и правильный спецификатор формата для этого %u
, Исправить printf()
позвоните и проверьте снова.