guitarist2404
@guitarist2404

Что нужно исправить в кодее сортировки merge, чтобы она правильно работала?

Нам по программированию задали сделать программу, в которой содержатся различные виды сортировок, в том числе merge_sort (сортировка слиянием). Каждому виду сортировок присвоен свой номер. После запуска программы пользователь с компьютера нажимает номер, и массив сортируется выбранной сортировкой с подсчётом времени работы.

Первые три сортировки работают корректно (clear не беру во внимание), а вот merge_sort (номер 8) после запуска выдаёт мне мусор в виде отрицательных шестизначных чисел.

Подскажите, пожалуйста, что не так в коде (возможно, ошибка содержится в main)

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <ctime>

void swap(int* a, int* b) {
	int c = *a;
	*a = *b;
	*b = c;
}

//CORRECT PROCESS...//
void sort(int mas[], int n) {
	int tmp, ind, min;
	for (int i = 0; i < n; i++) {
		min = mas[i];
		ind = i;
		for (int j = i; j < n; j++) {
			if (mas[j] < min) {
				min = mas[j];
				ind = j;
			}
		}
		swap(&mas[i], &mas[ind]);
	}
}

//CORRECT PROCESS...//
void count_sort(int* mas, int n) {
	int* p;
	p = (int*)malloc(101 * (sizeof(mas)));
	for (int i = 0; i < 101; i++) {
		p[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		++p[mas[i]];
	}
	int k = 0;
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < p[i]; j++) {
			mas[k] = i;
			k++;
		}
	}
	free(p);
}

//CORRECT PROCESS...//
void bubble(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[j] < arr[j - 1]) {
				swap(&arr[j], &arr[j - 1]);
			}
		}
	}
}

void clear(int arr[], int arr_res[], int n, int* p) {
	int k = 0; int flag = 0;
	for (int i = 0; i < n; i++) {
		flag = 0;
		for (int j = 0; j < k; j++) {
			if (arr_res[j] == arr[i]) {
				flag = 1;
				break;
			}
		}
		if (flag == 0) {
			arr_res[k] = arr[i];
			k++;
		}
	}
	*p = k;
}

<b>void merge(int mas[], int res[], int left, int right, int mid) {
	int i = left;
	int j = mid + 1;
	int k = left;
	while ((i <= mid) && (j <= right)) {
		if (res[i] < mas[j]) {
			res[k] = mas[i];
			i++;
		}
		else {
			res[k] = mas[j];
			j++;
			k++;
		}
		if (i > mid) {
			while (j <= right) {
				res[k] = mas[j];
				k++;
				j++;
			}
		}
		else {
			while (i <= mid) {
				res[k] = mas[i];
				k++;
				i++;
			}
		}
		for (int i = left; i <= right; i++) {
			mas[i] = res[i];
		}
	}
}

void merge_sort(int mas[], int res[], int left, int right) {
	if (left == right) {
		return;
	}
	int mid = (left + right) / 2;
	merge_sort(mas, res, left, mid);
	merge_sort(mas, res, mid+1, right);
	merge(mas, res, left, mid, right);
}</b>


void print_arr(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		printf("%d\n", arr[i]);
		}
	}

int main() {
	const int n = 51;
	int mas[n] = { 60, 32, 58, 40, 18, 90, 55, 68, 89, 95, 16, 84, 70, 68, 38, 20, 5, 20, 52, 95, 74, 65, 99, 70, 20, 59, 50 ,92, 17, 91, 69, 19, 29, 34, 41, 73, 44, 27, 68, 89, 24, 66, 81, 51, 44, 52, 74, 10, 83, 13 };
	int res[n];
	int num;
	int s;


	int left = 1, right = 51;
	int mid = (left + right) / 2;

	clock_t begin, end;
	

	printf("Menu: \n"
		"1. Sort\n"
		"2. Count_sort\n"
		"3. Bubble\n"
		"4. Clear\n"
		"8. Merge_sort\n"
		"0. Back\n"
		"Enter operation: ");
	scanf_s("%d", &num);
	printf("\n");

	begin = clock();

	switch (num)
	{

	case 1:
		sort(mas, n);
		for (int i = 0; i < n; i++) {
			printf("%d\n", mas[i]);
		}
		end = clock();
		printf("\n%d (ms)\n%.2f (s)", end - begin, (end - begin) / (float)CLOCKS_PER_SEC);
		break;

	case 2:
		count_sort(mas, n);
		for (int i = 0; i < n; i++) {
			printf("%d\n", mas[i]);
		}
		end = clock();
		printf("\n%d (ms)\n%.2f (s)", end - begin, (end - begin) / (float)CLOCKS_PER_SEC);
		break;

	case 3:
		bubble(mas, n);
		for (int i = 0; i < n; i++) {
			printf("%d\n", mas[i]);
		}
		end = clock();
		printf("\n%d (ms)\n%.2f (s)", end - begin, (end - begin) / (float)CLOCKS_PER_SEC);
		break;

	case 4:
		clear(mas, res, n, &s);
		for (int i = 0; i < n; i++) {
			printf("%d\n", res[i]);
		}
		break;


	<b>case 8:

		

		merge_sort(mas, res, left, right);
		for (int i = 0; i < n; i++) {
			printf("%d\n", res[i]);
		}
		end = clock();
		printf("\n%d (ms)\n%.2f (s)", end - begin, (end - begin) / (float)CLOCKS_PER_SEC);
		break;
</b>

	default:
		printf("Not found.\n\n");
	}
}
  • Вопрос задан
  • 70 просмотров
Пригласить эксперта
Ответы на вопрос 1
@res2001
Developer, ex-admin
Может быть потому, что массивы в С/С++ индексируются, начиная с нуля, следовательно последний элемент будет иметь индекс (n-1), т.е. 50. А вы передаете в merge_sort в качестве right значение 51. Так что у вас выход за пределы массива. Так же вы используете начальное значение для left = 1, таким образом вы не обрабатываете 0 элемент массива.

Кроме того. Заверните ваш код в тег code (кнопка </> на панели инструментов) и верните все отступы - код не возможно читать.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы