Cod sursa(job #3211122)

Utilizator BogdancxTrifan Bogdan Bogdancx Data 8 martie 2024 16:29:25
Problema Sortare prin comparare Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>

void Merge(int left, int mid, int right, std::vector<int>& v) {
	std::vector<int>a, b;
	for (int i = left; i <= mid; i++) {
		a.push_back(v[i]);
	}
	for (int i = mid + 1; i <= right; i++) {
		b.push_back(v[i]);
	}

	int i = 0, j = 0, n = a.size(), m = b.size(), k = left;

	while (i < n && j < m) {
		if (a[i] < b[j]) {
			v[k++] = a[i++];
		}
		else {
			v[k++] = b[j++];
		}
	}
	while (i < n) v[k++] = a[i++];
	while (j < m) v[k++] = b[j++];
}

void MergeSort(int left, int right, std::vector<int> &v) {
	if (left >= right) {
		return;
	}
	else {
		int mid = (left + right) / 2;

		MergeSort(left, mid, v);
		MergeSort(mid + 1, right, v);
		Merge(left, mid, right, v);
	}
}

int main() {
	std::ifstream fin("algsort.in");
	std::ofstream fout("algsort.out");

	int n, nr;
	std::vector<int>v;

	fin >> n;
	for (int i = 0; i < n; i++) {
		fin >> nr;
		v.push_back(nr);
	}

	MergeSort(0, n-1, v);

	for (int i = 0; i < n; i++)
		fout << v[i] << ' ';


	return 0;
}