CPSC200ProjectFinal/MergeSort.java at master · braem-schoolwork/CPSC200ProjectFinal · 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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import java.util.Arrays;


public class MergeSort implements Sort
{
//private data members
	sortParams sParams;

//constructors
	public MergeSort()
	{
		sParams = null;
	}
//initializer method
	public void initialize(sortParams s)
	{
		sParams = s;
	}
//getter
	public sortParams getSortParams()
	{
		return sParams;
	}

	void TestPeakUsage(int memUsage)
	{
		if(memUsage > sParams.getMemUsage())
		{
			sParams.setMemUsage(memUsage);
		}
	}

	/*
	 * Merge Sort Methods for Ascending/Descending
	 * (Logic for the sorting)
	 */
	void MSort(int[] arr, int arrSize, Direction dir, int memUsage)
	{
	//a full copy of the array gets copied each recursion
		memUsage += 32*(arrSize);
		TestPeakUsage(memUsage);
	//copies the arrays into 2 parts
		int[] LHS = Arrays.copyOfRange(arr, 0, arrSize/2);
		int[] RHS = Arrays.copyOfRange(arr, LHS.length, arrSize);
	//recursive step
		if(LHS.length>1)
		{
			MSort(LHS, LHS.length, dir, memUsage);
		}
		if(RHS.length>1)
		{
			MSort(RHS, RHS.length, dir, memUsage);
		}
		memUsage += 32;
		TestPeakUsage(memUsage);
		int L = 0;
		memUsage += 32;
		TestPeakUsage(memUsage);
		int R = 0;
	//merge step based on direction
		if(dir == Direction.ASCENDING)
		{
			memUsage += 32;
			TestPeakUsage(memUsage);
			for(int j=0; j<arrSize; ++j)
			{
				if((!(LHS.length==L) && !(RHS.length==R) && LHS[L]<RHS[R]) || RHS.length==R)
				{
					arr[j] = LHS[L];
					L++;
				}
				else if((!(LHS.length==L) && !(RHS.length==R) && LHS[L]>RHS[R]) || LHS.length==L)
				{
					arr[j] = RHS[R];
					R++;
				}
				else
				{
					arr[j] = LHS[L];
					j++;
					L++;
					arr[j] = RHS[R];
					R++;
				}
			}
			memUsage -= 32;
		}
		else
		{
			memUsage += 32;
			TestPeakUsage(memUsage);
			for(int j=0; j<arrSize; ++j)
			{
				if((!(LHS.length==L) && !(RHS.length==R) && LHS[L]>RHS[R]) || RHS.length==R)
				{
					arr[j] = LHS[L];
					L++;
				}
				else if((!(LHS.length==L) && !(RHS.length==R) && LHS[L]<RHS[R]) || LHS.length==L)
				{
					arr[j] = RHS[R];
					R++;
				}
				else
				{
					arr[j] = LHS[L];
					j++;
					L++;
					arr[j] = RHS[R];
					R++;
				}
			}
			memUsage -= 32;
		}
		memUsage -= 64;
	}
  /*
   * Sort Method Implementation
   * sorts in order the input has using the private MergeSort
   * methods above
   */
	public void sort(sortParams sParams)
	{
		int memUsage = 0;
		MSort(sParams.getArray(), sParams.getArray().length, sParams.getDirection(), memUsage);
	}
}