scheduling_project/Utility.cpp at master · Niloqui/scheduling_project · 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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include "Utility.hpp"

int absoluteDifference(int a, int b) {
	return a >= b ? a - b : b - a;
}

void mergeSortFin(int* A, int* B, int n, int a, int b) {
	int m = (a + b) / 2, i = a, j = m + 1;

	for (int k = a; k <= b; k++) {
		if (i > m) {
			B[k] = A[j];
			j++;
		}
		else if (j > b) {
			B[k] = A[i];
			i++;
		}
		else if (A[i] <= A[j]) {
			B[k] = A[i];
			i++;
		}
		else {
			B[k] = A[j];
			j++;
		}
	}

	for (int k = a; k <= b; k++) {
		A[k] = B[k];
	}
}

void mergeSortRec(int* A, int* B, int n, int i, int j) {
	if (i >= j)
		return;

	mergeSortRec(A, B, n, i, (i + j) / 2);
	mergeSortRec(A, B, n, 1 + (i + j) / 2, j);
	mergeSortFin(A, B, n, i, j);
}

void mergeSort(int* A, int n) {
	int* B = new int[n];

	mergeSortRec(A, B, n, 0, n - 1);
	delete[] B;
}

void mergeSortFin(int* A1, int* A2, int* B1, int* B2, int n, int a, int b) {
	int m = (a + b) / 2, i = a, j = m + 1;

	for (int k = a; k <= b; k++) {
		if (i > m) {
			B2[k] = A2[j];
			B1[k] = A1[j];
			j++;
		}
		else if (j > b) {
			B2[k] = A2[i];
			B1[k] = A1[i];
			i++;
		}
		else if (A2[i] <= A2[j]) {
			B2[k] = A2[i];
			B1[k] = A1[i];
			i++;
		}
		else {
			B2[k] = A2[j];
			B1[k] = A1[j];
			j++;
		}
	}

	for (int k = a; k <= b; k++) {
		A1[k] = B1[k];
		A2[k] = B2[k];
	}
}

void mergeSortRec(int* A1, int* A2, int* B1, int* B2, int n, int i, int j) {
	if (i >= j)
		return;

	mergeSortRec(A1, A2, B1, B2, n, i, (i + j) / 2);
	mergeSortRec(A1, A2, B1, B2, n, 1 + (i + j) / 2, j);
	mergeSortFin(A1, A2, B1, B2, n, i, j);
}

void mergeSort(int* A1, int* A2, int n) {
	int* B1, * B2;
	B1 = new int[n];
	B2 = new int[n];

	mergeSortRec(A1, A2, B1, B2, n, 0, n - 1);
}

void reverseVector(int* vect, int n) {
	int* temp = new int[n];
	int i;

	for (i = 0; i < n; i++)
		temp[i] = vect[i];

	for (i = 0; i < n; i++)
		vect[i] = temp[n-1-i];

	delete [] temp;
}