Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.06.2021, 22:27   #1
relel
Новичок
Джуниор
 
Регистрация: 19.06.2021
Сообщений: 1
Сообщение Сортировка массива MergeSort

Помогите ,пожалуйста, решить проблему. Нужно, где жирным написано вместо Merge() функции, которая написана нами, использовать функцию merge() из stl библиотеки
Код:
#include <iostream> 
#include <random>
#include<vector>
#include<algorithm>
#include <ctime>
using namespace std;

//нерекурсивная восходящая версия алгоритма сортировки слиянием


//Двухпутевое слияние
//с построением битонной последовательности


template <typename T>
void MergeSort(T* RES, int left, int m, int right) {
	int i, j;
	//вспомогательный массив
	T* WORK = new T[right + 1];
	//построение битонной последовательности
	for (i = m + 1; i > left; i--)
		WORK[i - 1] = RES[i - 1];
	for (j = m; j < right; j++)
		WORK[right + m - j] = RES[j + 1];
	//выполнение слияния
	for (int k = left; k <= right; k++)
		if (WORK[j] < WORK[i])
			RES[k] = WORK[j--];
		else
			RES[k] = WORK[i++];
	delete[] WORK;
}



template <class Item>
void UPsort(Item a[], int left, int right)
{
	for (int m = 1; m <= right - left; m = m + m)
		for (int i = left; i <= right - m; i += m + m)
			MergeSort(a, i, i + m - 1, min(i + m + m - 1, right));
}

//Рекурсивная нисходящая версия алгоритма сортировки слиянием:
//функция, сливающая массивы
template <typename T>
void Merge(T* A, int left, int right)
{
	int middle, start, final, j;
	double* mas = new double[100];
	middle = (left + right) / 2; //вычисление среднего элемента
	start = left; //начало левой части
	final = middle + 1; //начало правой части
	for (j = left; j <= right; j++) { //выполнять от начала до конца
		if ((start <= middle) && ((final > right) || (A[start] < A[final])))
		{
			mas[j] = A[start];
			start++;
		}
		else
		{
			mas[j] = A[final];
			final++;
		}
	}
	//возвращение результата в список
	for (j = left; j <= right; j++) A[j] = mas[j];
	delete[]mas;
};


//рекурсивная процедура сортировки
template <typename T>
void DownSort(T* A, int left, int right)
{
	if (left < right)
	{
		DownSort(A, left, (left + right) / 2); //сортировка левой части
		DownSort(A, (left + right) / 2 + 1, right); //сортировка правой части
		Merge(A, left, right); //слияние двух частей
		
		//merge(A+left, A+(left + right) / 2 -1, A+(left + right) / 2 + 1, A+right -1 , A+left);
		//inplace_merge(A + left, A + (left + right) / 2, A + right); Мои попытки
		
	}
	/*if (left - right == 1) {
		
	}*/
};






void main()
{

	setlocale(LC_ALL, "Rus");
	// Создание генератора случайных чисел
	// с начальным состоянием
	mt19937 gen(time(0));

	int left = 0;
	int const right = 30;
	double mas[right + 1];
	// Порождение целых чисел 
	// в интервале от 10 до 50,
	// распределение получает генератор как аргумент
	uniform_int_distribution<> di(10, 50);
	for (int i = 0; i <= right; ++i)
	{
		mas[i] = di(gen);
		cout << mas[i] << " ";
	}
	cout << endl << endl;

	UPsort(mas, left, right);

	cout << "Упорядоченный массив: "; //вывод упорядоченного массива
	for (int i = 1; i <= right; i++) cout << mas[i] << " ";

	cout << endl << endl;

	// Порождение чисел с плавающей точкой
	// в интервале от 10.0 до 50.0, 
	// распределение получает генератор как аргумент
	int left1 = 0;
	int const right1 = 10;
	double mas1[right1 + 1];
	uniform_real_distribution<> dr(10, 50);

	for (int j = 0; j <= right1; ++j)
	{
		mas1[j] = dr(gen);
		cout << mas1[j] << " ";
	}

	cout << endl << endl;

	DownSort(mas1, left1, right1);

	cout << "Упорядоченный массив:Ф "; //вывод упорядоченного массива
	for (int j = 0; j <= right1; j++) cout << mas1[j] << " ";
}

Последний раз редактировалось relel; 19.06.2021 в 22:32.
relel вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Где ошибка (Си)Mergesort Sterben Помощь студентам 3 12.05.2015 23:33
Быстрая сортировка(сортировка Хоара). Сортировка фрагмента массива [C++] druger Помощь студентам 0 20.04.2012 15:49
Сортировка массива student_92 Помощь студентам 0 20.03.2012 21:20
Сортировка массива методами предсортировки и слияния, и пирамидальная сортировка. lenny_24 Помощь студентам 2 17.04.2011 18:57
Сортировка массива natt23 Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 3 22.11.2010 10:49