abignumscalc/calculator.cpp at master · jojaquix/abignumscalc · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <numeric>

#include "calculator.h"

using namespace std;
using namespace boost::multiprecision;
using namespace alert::bignums;

vector<uint1024_t> Operations::sort(vector<uint1024_t>& nums)
{
	//se usa qsort basad en indices
	vector<int> idx(nums.size());
	std::iota(std::begin(idx), std::end(idx), 0);

	qsort(nums, idx, idx.front(), idx.back());

	//se copian los valores en el orden adecuado;
	vector<uint1024_t> res;

	for (auto& i : idx)
	{
		res.push_back(nums[i]);
	}

	return res;

}

uint1024_t Operations::sum(vector<uint1024_t>& nums)
{
	uint1024_t acum = 0;
	std::for_each(std::begin(nums), std::end(nums),
		[&](uint1024_t n)
	{
		acum += n;
	}
	);

	return acum;
}

void  Operations::qsort(vector<uint1024_t>& nums, vector<int>& idx, int p, int q)
{
	int r;
	if (p < q)
	{
		r = partition(nums, idx, p, q);
		qsort(nums, idx, p, r - 1);
		qsort(nums, idx, r + 1, q);
	}
}

int  Operations::partition(vector<uint1024_t>& nums, vector<int>& idx, int p, int q)
{
	int left;
	int right;

	auto pivot = nums[idx[p]];
	left = p;
	right = q;

	while (left < right)
	{
		while (nums[idx[right]] > pivot)
		{
			right--;
		}
		while ((left < right) && ((nums[idx[left]] <= pivot)))
		{
			left++;
		}

		if (left < right)
		{
			swap(idx[left], idx[right]);
		}
	}

	swap(idx[p], idx[right]);

	return right;
}