Подразделы

Другие разделы

Дата и время

11/12/2024 14:02:01

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

print2314. (алгоритмы) Сортировка массива слиянием

print(алгоритмы) Сортировка массива слиянием

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Необходимо реализовать сортировку слиянием на массиве.
В следующем шаблоне 2 прототипа функций, для рекурсивного вызова разделения и слияния соответственно.
Но нет требований именно на рекурсивную реализацию, можете реализовать всё в одной функции.
#include <iostream>
#include <time.h>

using namespace std;

// прототипы функций
void merge(int*, int, int);
void mergeRec(int*, int, int);
int N;

int main() {
	cin >> N; // количество входных элементов
	// если пригодится для отладки, генератор случайных чисел
	// srand(time(NULL)); // инициализатор генератора
	// rand()%99 + 1: сгенерирует случайное число от 1 до 99.

	int* A = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> A[i]; // заполнение массива
	}        
	mergeRec(A, 0, N-1); // вызов сортировки
        
        for (int i = 0; i < N; i++) {
		cout << A[i] << " "; // печать
	}
	return 0;
}

void mergeRec(int* A, int left, int right) {
	// рекурсивный вызов разделения, затем вызов слияния
	// необходимо реализовать

}

void merge(int *A, int left, int right){
	// процедура для слияния A[left .. mid] и A[mid+1 .. right];
	// необходимо реализовать

}; 
Ввод
Число N – количество входных элементов, затем N чисел массива.
Вывод
Функция вывода написана – элементы массива через пробел.

Пример ввода

5 5 4 3 2 1

Пример вывода

1 2 3 4 5 
loading