-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSorting.java
165 lines (142 loc) · 4.48 KB
/
Sorting.java
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/**
* Name: Qixuan "Harrison" Ma
* Email: [email protected]
*
* this file is an implementation of 2 sorting methods, merge sort and
* insertion sort
* this is a generic class whose type parameter extends Comparable
* there will be 3 public methods in this file,
* one for insertion sort and two for merge sort
*/
import java.util.Arrays;
/**
* the class Sorting is a generic class whose type extends the Comparable
* interface. it has 3 public methods, one for insertion sort and two for
* merge sort. it will use the imported Arrays
*/
public class Sorting<E extends Comparable<E>>
{
// 2 constants that I will use for dividing the array
private static final int CONSTANT_TWO = 2;
private static final int CONSTANT_FOUR = 4;
/**
* this method is a custom implementation of the Insertion Sort algorithm
* we will use Arrays.toString() to print out the array
* @param array to be sorted
*/
public void insertionSort(E[] array)
{
// throw a NullPointerException if the input array is null
if (array == null)
{
throw new NullPointerException();
}
// throw a NullPointerException if any element in the array is null
for (E e : array)
{
if (e == null)
{
throw new NullPointerException();
}
}
int len = array.length;
for (int i = 0; i < len; i ++)
{
E curr = array[i];
int j = i - 1;
while (j >= 0 && (array[j].compareTo(curr) > 0))
{
array[j + 1] = array[j];
j --;
}
array[j + 1] = curr;
System.out.println(Arrays.toString(array));
}
}
/**
* this method is a custom implementation of the Merge Sort algorithm
* we will use Arrays.toString() to print out the array
* the merge method will be used in this method
* @param array to be sorted
*/
public void mergeSort(E[] array)
{
// throw a NullPointerException if the input array is null
if (array == null)
{
throw new NullPointerException();
}
// throw a NullPointerException if any element in the array is null
for (E e : array)
{
if (e == null)
{
throw new NullPointerException();
}
}
int len = array.length;
int splitInd = 0;
if (len > 1)
{
// apply the normal half method
if (len < CONSTANT_FOUR)
{
splitInd = len / CONSTANT_TWO;
}
// apply the 1:3 ratio method
else
{
splitInd = len / CONSTANT_FOUR;
}
E[] leftArray = Arrays.copyOfRange(array, 0, splitInd);
E[] rightArray = Arrays.copyOfRange(array, splitInd, len );
int left = leftArray.length;
int right = rightArray.length;
// System.out.println("Left array is: " + Arrays.toString(leftArray));
// System.out.println("Right array is: " + Arrays.toString(rightArray));
mergeSort(leftArray);
mergeSort(rightArray);
merge(array, leftArray, rightArray, left, right);
System.out.println(Arrays.toString(array));
}
}
/**
* this method merges two separate arrays together
* @param complete array, left array, right array,
* @param left array size, right array size
*/
public void merge(E[] array, E[] leftArray, E[] rightArray,
int left, int right)
{
int counter = 0;
int rightPos = 0;
int leftPos = 0;
while (leftPos < left && rightPos < right)
{
if (leftArray[leftPos].compareTo(rightArray[rightPos]) < 0)
{
array[counter] = leftArray[leftPos];
leftPos ++;
counter ++;
}
else
{
array[counter] = rightArray[rightPos];
rightPos ++;
counter ++;
}
}
while (leftPos < left)
{
array[counter] = leftArray[leftPos];
counter ++;
leftPos ++;
}
while (rightPos < right)
{
array[counter] = rightArray[rightPos];
counter ++;
rightPos ++;
}
}
}