Member 13763946 Ответов: 4

Как мне заставить эту mergesort работать?


В настоящее время я работаю над сортировкой массивов, и мне пришло время научиться сортировке слиянием, но пока я пытался кодировать, он компилируется, но Windows перестает работать. В чем может быть проблема?
int* mergeSort(int* arr){
	int size= sizeof(arr)/sizeof(arr[0]);
	if(size==1) return arr;
	
	int middle= size/2;
	int* rightArr= (int*)malloc(sizeof(int)*middle);
	int* leftArr= (int*)malloc(sizeof(int)*middle);
	
	for(int i=0; i<middle; i++){
		leftArr[i]= arr[i];
	} 
	
	for(int j=middle+1; j<size; j++){
		rightArr[j]= arr[j];
	}
	
	leftArr= mergeSort(leftArr);
	rightArr= mergeSort(rightArr);
	
	arr= merge(leftArr,rightArr);
	
	return arr;
}


Что я уже пробовал:

Я несколько раз пытался изменить код, но все равно получаю ту же ошибку (windows перестает работать).

Mohibur Rashid

Вы пытались изменить свой код, и вы все еще получаете ту же ошибку, какую ошибку?

Member 13763946

Как я уже упоминал, код компилируется правильно, но windows перестает работать во время выполнения кода.

4 Ответов

Рейтинг:
27

Jochen Arndt

Цитата:
он компилируется, но Windows перестает работать
Это не очень хорошее описание проблемы. Windows-это операционная система, и она обычно не "перестает работать" при запуске программы, которая ведет себя непредсказуемо.

Вы имеете в виду, что ваше приложение (главное окно) больше не отвечает?
Затем используйте отладчик для пошагового запуска приложения и проверки переменных.

Вы должны были показать также код самого merge() функция и то, как вы вызываете функцию сортировки.

Однако в вашем коде есть по крайней мере две большие ошибки и еще две другие

Первый большой:
int size= sizeof(arr)/sizeof(arr[0]);
arr иметь тип int* так что sizeof(arr) это 4 или 8 в зависимости от типа приложения (32 или 64 бит). Разделив это на sizeof(int) привести size существование всегда 1 или 2.

Решение заключается в добавлении параметра функции, определяющего количество элементов в массиве:
int* mergeSort(int* arr, int items);

Второй большой и другие:
int middle= size/2;
int* rightArr= (int*)malloc(sizeof(int)*middle);
// ...
for(int j=middle+1; j<size; j++){
    rightArr[j]= arr[j];
}
rightArr имеет middle (size/2) элементы, но вы присваиваете значения, начиная с middle+1. Это доступ на запись вне связанного массива!
Я ожидал бы чего-то вроде:
for(int i = 0, j=middle; i<middle; i++, j++){
    rightArr[i]= arr[j];
}
Обратите также внимание, что я изменил начальный индекс для arr от middle+1 к middle (другая ошибка).

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


Рейтинг:
2

Richard MacCutchan

int* mergeSort(int* arr){
    int size= sizeof(arr)/sizeof(arr[0]);

Переменная arr объявляется как int* тип, так что его размер равен 4, и arr[0] является int тип, так что его размер тоже 4. Так что size всегда будет равно 1.


CPallini

5.

Рейтинг:
2

Patrice T

В языке Си массив-это просто его содержимое, размер которого нигде не хранится вместе с массивом. Вы должны отслеживать размер массива явно в переменной.

Когда вы не понимаете, что делает ваш код, отладчик позволяет вам выполнять код строка за строкой и проверять переменные.
Существует инструмент, который позволяет вам видеть, что делает ваш код, его имя отладчик Это также отличный инструмент обучения, потому что он показывает вам реальность, и вы можете увидеть, какие ожидания соответствуют реальности.
Когда вы не понимаете, что делает ваш код или почему он делает то, что он делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.

Отладчик - Википедия, свободная энциклопедия[^]

Освоение отладки в Visual Studio 2010 - руководство для начинающих[^]
Базовая отладка с помощью Visual Studio 2010 - YouTube[^]
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.


Рейтинг:
2

KarstenK

Если middle-это даже не то, что ваш код полностью неверен. Вы абсолютно упускаете некоторую сортировку в своем коде.

Для лучшего понимания прочтите следующее Статья Rosettacode о сортировке слиянием. Вы также найдете там некоторый код C.

И последнее, но не менее важное: вам нужно освободить выделенную память с помощью malloc.

Удачи - она вам понадобится. ;-)