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

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

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

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 06.05.2013, 14:12   #1
Rostislav2
Новичок
Джуниор
 
Регистрация: 06.05.2013
Сообщений: 1
По умолчанию Количество перестановок. Сортировка слиянием

Нужно найти минимальное количество перестановок соседних элементов последовательности, необходимое для того, чтобы отсортировать ее по возрастанию. Пробовал просто посчитать кол-во шагов, за которое сортировка пузырьком сделает это - не проходит по времени. Посоветовали сортировку слиянием использовать.
Вот, что вышло
Код:
#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;
int tmp;
vector<int>mas;
int merge(vector<int>&mas, int l, int m, int r)
{
	int per = 0;
	vector<int> buffer(r - l + 1);
	int pos1 = l;
	int pos2 = m+1;
	int posB = 0;

	while(pos1 <=m && pos2<=r)
	{
		if(mas[pos1] < mas[pos2])
			buffer[posB++] = mas[pos1++];
		else
		{
			buffer[posB++] = mas[pos2++];
			per+=m-pos1 + l;
		}
	}

	while (pos1 <=m)
		buffer[posB++] = mas[pos1++];
	while (pos2 <=r)
		buffer[posB++] = mas[pos2++];
	copy(buffer.begin(), buffer.end(), mas.begin()+l);
	return per;

}
int merge_sort(vector<int> & mas, int l, int r)
{
	int per = 0;
	if(l == r)
		return per;
	int m = (l + r)/2;
	per +=merge_sort(mas, l,m);
	per +=merge_sort(mas, m+1,r);
	per += merge(mas, l, m, r);
	return per;
}
void input()
{
	int n ;
	vector<int> mas;
	scanf("%d", &n);
	mas.resize(n);
	for(int i = 0; i < n; i++)
		scanf("%d", &mas[i]);
	int per = merge_sort(mas,0,n-1);
	tmp = per;
}
void output()
{
    cout<<tmp;
}
int main()
{
	input();
	output();
}
Но почему-то не правильно программа считает

Последний раз редактировалось Rostislav2; 06.05.2013 в 14:15.
Rostislav2 вне форума Ответить с цитированием
Ответ


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

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сортировка слиянием. С++ Noizik Помощь студентам 1 09.05.2012 14:23
сортировка слиянием (C++) DarkAltair Помощь студентам 7 11.10.2011 21:12
Сортировка перестановок C sharp WOWka777 C# (си шарп) 0 09.11.2010 22:20
Сортировка слиянием Aндрей Общие вопросы C/C++ 3 15.04.2010 09:47
Сортировка слиянием maxflint Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 5 05.12.2009 20:41