|
1 | 1 | packageSorts; |
2 | 2 |
|
3 | | -importjava.lang.Math; |
4 | 3 | importjava.util.Random; |
5 | 4 |
|
6 | 5 | /** |
7 | 6 | * @author [Hemanth Kotagiri](https://github.com/hemanth-kotagiri) |
8 | 7 | * @see [Tim Sort](https://en.wikipedia.org/wiki/Tim_sort) |
9 | 8 | */ |
10 | | - |
11 | 9 | classTimSort { |
12 | | -intarray[]; |
13 | | -intarray_length; |
14 | | -intRUN =32; |
15 | | - |
16 | | -/** |
17 | | - * @brief A constructor which takes in the array specified by the user. |
18 | | - * @param array : Array given by the user. |
19 | | - */ |
20 | | - |
21 | | -publicTimSort(int[]array) { |
22 | | -this.array =array; |
23 | | -this.array_length =array.length; |
| 10 | +intarray[]; |
| 11 | +intarray_length; |
| 12 | +intRUN =32; |
| 13 | + |
| 14 | +/** |
| 15 | + * @brief A constructor which takes in the array specified by the user. |
| 16 | + * @param array : Array given by the user. |
| 17 | + */ |
| 18 | +publicTimSort(int[]array) { |
| 19 | +this.array =array; |
| 20 | +this.array_length =array.length; |
| 21 | + } |
| 22 | + |
| 23 | +/** |
| 24 | + * @brief A constructor which takes in an array length and randomly initializes an array. |
| 25 | + * @param array_length length given by the user. |
| 26 | + */ |
| 27 | +publicTimSort(intarray_length) { |
| 28 | +Randomrand =newRandom(); |
| 29 | + |
| 30 | +this.array_length =array_length; |
| 31 | +this.array =newint[this.array_length]; |
| 32 | + |
| 33 | +for (inti =0;i <this.array_length;i++) { |
| 34 | +intrandom_number =rand.nextInt(1000); |
| 35 | +this.array[i] =random_number; |
24 | 36 | } |
25 | | - |
26 | | -/** |
27 | | - * @brief A constructor which takes in an array length and randomly |
28 | | - * initializes an array. |
29 | | - * @param array_length length given by the user. |
30 | | - */ |
31 | | - |
32 | | -publicTimSort(intarray_length) { |
33 | | -Randomrand =newRandom(); |
34 | | - |
35 | | -this.array_length =array_length; |
36 | | -this.array =newint[this.array_length]; |
37 | | - |
38 | | -for (inti =0;i <this.array_length;i++) { |
39 | | -intrandom_number =rand.nextInt(1000); |
40 | | -this.array[i] =random_number; |
41 | | - } |
| 37 | + } |
| 38 | + |
| 39 | +/** |
| 40 | + * @brief A method to change the size of the run. |
| 41 | + * @param run : Value specified by the user to change the run. |
| 42 | + */ |
| 43 | +publicvoidchange_run(intrun) { |
| 44 | +this.RUN =run; |
| 45 | + } |
| 46 | + |
| 47 | +/** |
| 48 | + * @brief A default constructor when no parameters are given. Initializes the array length to be |
| 49 | + * 100. Generates a random number array of size 100. |
| 50 | + */ |
| 51 | +publicTimSort() { |
| 52 | +this.array_length =100; |
| 53 | +this.array =newint[this.array_length]; |
| 54 | + |
| 55 | +Randomrand =newRandom(); |
| 56 | +for (inti =0;i <this.array_length;i++) { |
| 57 | +intrandom_number =rand.nextInt(1000); |
| 58 | +this.array[i] =random_number; |
42 | 59 | } |
43 | | - |
44 | | -/** |
45 | | - * @brief A method to change the size of the run. |
46 | | - * @param run : Value specified by the user to change the run. |
47 | | - */ |
48 | | - |
49 | | -publicvoidchange_run(intrun) { |
50 | | -this.RUN =run; |
| 60 | + } |
| 61 | + |
| 62 | +/** |
| 63 | + * @brief Performs Insertion Sort Algorithm on given array with bounded indices. |
| 64 | + * @param array: The array on which the algorithm is to be performed. |
| 65 | + * @param start_idx: The starting index from which the algorithm is to be performed. |
| 66 | + * @param end_idx: The ending index at which the algorithm needs to stop sorting. |
| 67 | + */ |
| 68 | +publicvoidinsertion_sort(int[]array,intstart_idx,intend_idx) { |
| 69 | +for (inti =0;i <array.length;i++) { |
| 70 | +intcurrent_element =array[i]; |
| 71 | +intj =i -1; |
| 72 | +while (j >=0 &&array[j] >current_element) { |
| 73 | +array[j +1] =array[j]; |
| 74 | +j--; |
| 75 | + } |
| 76 | +array[j +1] =current_element; |
51 | 77 | } |
52 | | - |
53 | | -/** |
54 | | - * @brief A default constructor when no parameters are given. |
55 | | - * Initializes the array length to be 100. |
56 | | - * Generates a random number array of size 100. |
57 | | - */ |
58 | | - |
59 | | -publicTimSort() { |
60 | | -this.array_length =100; |
61 | | -this.array =newint[this.array_length]; |
62 | | - |
63 | | -Randomrand =newRandom(); |
64 | | -for (inti =0;i <this.array_length;i++) { |
65 | | -intrandom_number =rand.nextInt(1000); |
66 | | -this.array[i] =random_number; |
67 | | - } |
| 78 | + } |
| 79 | + |
| 80 | +/** |
| 81 | + * @brief A method to merge two runs(chunks of array). |
| 82 | + * @param array: The origin array which is to be sorted. |
| 83 | + * @param start: Starting index of the first run(chunk). |
| 84 | + * @param mid: The ending index of the first run(chunk). |
| 85 | + * @param end: Ending index of the second run(chunk). |
| 86 | + */ |
| 87 | +publicvoidmerge_runs(intarray[],intstart,intmid,intend) { |
| 88 | + |
| 89 | +intfirst_array_size =mid -start +1,second_array_size =end -mid; |
| 90 | +intarray1[] =newint[first_array_size],array2[] =newint[second_array_size]; |
| 91 | +inti =0,j =0,k =0; |
| 92 | + |
| 93 | +// Building the two sub arrays from the array to merge later |
| 94 | +for (i =0;i <first_array_size;i++)array1[i] =array[start +i]; |
| 95 | +for (i =0;i <second_array_size;i++)array2[i] =array[mid +1 +i]; |
| 96 | + |
| 97 | +i =0; |
| 98 | +j =0; |
| 99 | +k =start; |
| 100 | + |
| 101 | +while (i <first_array_size &&j <second_array_size) { |
| 102 | +if (array1[i] <=array2[j]) { |
| 103 | +array[k] =array1[i]; |
| 104 | +i++; |
| 105 | + }else { |
| 106 | +array[k] =array2[j]; |
| 107 | +j++; |
| 108 | + } |
| 109 | +k++; |
68 | 110 | } |
69 | 111 |
|
70 | | -/** |
71 | | - * @brief Performs Insertion Sort Algorithm on given array with bounded |
72 | | - * indices. |
73 | | - * @param array: The array on which the algorithm is to be performed. |
74 | | - * @param start_idx: The starting index from which the algorithm is to be |
75 | | - * performed. |
76 | | - * @param end_idx: The ending index at which the algorithm needs to stop |
77 | | - * sorting. |
78 | | - */ |
79 | | - |
80 | | -publicvoidinsertion_sort(int[]array,intstart_idx,intend_idx) { |
81 | | -for (inti =0;i <array.length;i++) { |
82 | | -intcurrent_element =array[i]; |
83 | | -intj =i -1; |
84 | | -while (j >=0 &&array[j] >current_element) { |
85 | | -array[j +1] =array[j]; |
86 | | -j--; |
87 | | - } |
88 | | -array[j +1] =current_element; |
89 | | - } |
| 112 | +while (i <first_array_size) { |
| 113 | +array[k] =array1[i]; |
| 114 | +k++; |
| 115 | +i++; |
90 | 116 | } |
91 | 117 |
|
92 | | -/** |
93 | | - * @brief A method to merge two runs(chunks of array). |
94 | | - * @param array: The origin array which is to be sorted. |
95 | | - * @param start: Starting index of the first run(chunk). |
96 | | - * @param mid: The ending index of the first run(chunk). |
97 | | - * @param end: Ending index of the second run(chunk). |
98 | | - */ |
99 | | - |
100 | | -publicvoidmerge_runs(intarray[],intstart,intmid,intend) { |
101 | | - |
102 | | -intfirst_array_size =mid -start +1,second_array_size =end -mid; |
103 | | -intarray1[] =newint[first_array_size],array2[] =newint[second_array_size]; |
104 | | -inti =0,j =0,k =0; |
105 | | - |
106 | | -// Building the two sub arrays from the array to merge later |
107 | | -for (i =0;i <first_array_size;i++) |
108 | | -array1[i] =array[start +i]; |
109 | | -for (i =0;i <second_array_size;i++) |
110 | | -array2[i] =array[mid +1 +i]; |
111 | | - |
112 | | -i =0; |
113 | | -j =0; |
114 | | -k =start; |
115 | | - |
116 | | -while (i <first_array_size &&j <second_array_size) { |
117 | | -if (array1[i] <=array2[j]) { |
118 | | -array[k] =array1[i]; |
119 | | -i++; |
120 | | - }else { |
121 | | -array[k] =array2[j]; |
122 | | -j++; |
123 | | - } |
124 | | -k++; |
125 | | - } |
126 | | - |
127 | | -while (i <first_array_size) { |
128 | | -array[k] =array1[i]; |
129 | | -k++; |
130 | | -i++; |
131 | | - } |
132 | | - |
133 | | -while (j <second_array_size) { |
134 | | -array[k] =array2[j]; |
135 | | -k++; |
136 | | -j++; |
137 | | - } |
| 118 | +while (j <second_array_size) { |
| 119 | +array[k] =array2[j]; |
| 120 | +k++; |
| 121 | +j++; |
138 | 122 | } |
139 | | - |
140 | | -/** |
141 | | - * @brief Tim Sort Algorithm method. |
142 | | - */ |
143 | | - |
144 | | -publicvoidalgorithm() { |
145 | | -// Before Sorting |
146 | | -System.out.println("Before sorting the array: "); |
147 | | -this.showArrayElements(); |
148 | | -System.out.println(); |
149 | | - |
150 | | -// Applying insertion sort on RUNS. |
151 | | -for (inti =0;i <this.array_length;i +=this.RUN) |
152 | | -this.insertion_sort(this.array,i,Math.min(i +this.RUN, (this.array_length -1))); |
153 | | - |
154 | | -for (intsplit =this.RUN;split <this.array_length;split =2 *split) { |
155 | | -for (intstart_idx =0;start_idx <this.array_length;start_idx +=2 *split) { |
156 | | -intmid =start_idx +split -1; |
157 | | -intend_idx =Math.min((start_idx +2 *split -1), (this.array_length -1)); |
158 | | - |
159 | | -this.merge_runs(this.array,start_idx,mid,end_idx); |
160 | | - } |
161 | | - } |
162 | | -// After sorting |
163 | | -System.out.println("After sorting the array: "); |
164 | | -this.showArrayElements(); |
165 | | -System.out.println(); |
| 123 | + } |
| 124 | + |
| 125 | +/** @brief Tim Sort Algorithm method. */ |
| 126 | +publicvoidalgorithm() { |
| 127 | +// Before Sorting |
| 128 | +System.out.println("Before sorting the array: "); |
| 129 | +this.showArrayElements(); |
| 130 | +System.out.println(); |
| 131 | + |
| 132 | +// Applying insertion sort on RUNS. |
| 133 | +for (inti =0;i <this.array_length;i +=this.RUN) |
| 134 | +this.insertion_sort(this.array,i,Math.min(i +this.RUN, (this.array_length -1))); |
| 135 | + |
| 136 | +for (intsplit =this.RUN;split <this.array_length;split =2 *split) { |
| 137 | +for (intstart_idx =0;start_idx <this.array_length;start_idx +=2 *split) { |
| 138 | +intmid =start_idx +split -1; |
| 139 | +intend_idx =Math.min((start_idx +2 *split -1), (this.array_length -1)); |
| 140 | + |
| 141 | +this.merge_runs(this.array,start_idx,mid,end_idx); |
| 142 | + } |
166 | 143 | } |
167 | | - |
168 | | -/** |
169 | | - * @brief A method to show the elements inside the array. |
170 | | - */ |
171 | | - |
172 | | -publicvoidshowArrayElements() { |
173 | | -for (inti =0;i <this.array.length;i++) { |
174 | | -System.out.print(this.array[i] +" "); |
175 | | - } |
176 | | -System.out.println(); |
| 144 | +// After sorting |
| 145 | +System.out.println("After sorting the array: "); |
| 146 | +this.showArrayElements(); |
| 147 | +System.out.println(); |
| 148 | + } |
| 149 | + |
| 150 | +/** @brief A method to show the elements inside the array. */ |
| 151 | +publicvoidshowArrayElements() { |
| 152 | +for (inti =0;i <this.array.length;i++) { |
| 153 | +System.out.print(this.array[i] +" "); |
| 154 | + } |
| 155 | +System.out.println(); |
| 156 | + } |
| 157 | + |
| 158 | +/** @brief A method to test the sorting algorithm */ |
| 159 | +staticvoidtest() { |
| 160 | +int[]array = {4,1,3,17,12,11,8}; |
| 161 | +TimSortsorterObj1 =newTimSort(); |
| 162 | +TimSortsorterObj2 =newTimSort(50); |
| 163 | +TimSortsorterObj3 =newTimSort(array); |
| 164 | + |
| 165 | +sorterObj1.algorithm(); |
| 166 | +sorterObj2.algorithm(); |
| 167 | +sorterObj3.algorithm(); |
| 168 | + |
| 169 | +// Testing the first array |
| 170 | +for (inti =0;i <sorterObj1.array_length -1;i++) { |
| 171 | +assert ((sorterObj1.array[i] <=sorterObj1.array[i +1])) :"Array is not sorted"; |
177 | 172 | } |
178 | 173 |
|
179 | | -/** |
180 | | - * @brief A method to test the sorting algorithm |
181 | | - */ |
182 | | - |
183 | | -staticvoidtest() { |
184 | | -int[]array = {4,1,3,17,12,11,8 }; |
185 | | -TimSortsorterObj1 =newTimSort(); |
186 | | -TimSortsorterObj2 =newTimSort(50); |
187 | | -TimSortsorterObj3 =newTimSort(array); |
188 | | - |
189 | | - |
190 | | -sorterObj1.algorithm(); |
191 | | -sorterObj2.algorithm(); |
192 | | -sorterObj3.algorithm(); |
193 | | - |
194 | | -// Testing the first array |
195 | | -for(inti =0;i <sorterObj1.array_length -1;i++) { |
196 | | -assert((sorterObj1.array[i] <=sorterObj1.array[i +1])) :"Array is not sorted"; |
197 | | - } |
198 | | - |
199 | | -// Testing the second array. |
200 | | -for(inti =0;i <sorterObj2.array_length -1;i++) { |
201 | | -assert((sorterObj2.array[i] <=sorterObj2.array[i +1])) :"Array is not sorted"; |
202 | | - } |
203 | | - |
204 | | -// Testing the third array. |
205 | | -for(inti =0;i <sorterObj3.array_length -1;i++) { |
206 | | -assert((sorterObj3.array[i] <=sorterObj3.array[i +1])) :"Array is not sorted"; |
207 | | - } |
| 174 | +// Testing the second array. |
| 175 | +for (inti =0;i <sorterObj2.array_length -1;i++) { |
| 176 | +assert ((sorterObj2.array[i] <=sorterObj2.array[i +1])) :"Array is not sorted"; |
208 | 177 | } |
209 | 178 |
|
210 | | -publicstaticvoidmain(String[]args) { |
211 | | -test(); |
| 179 | +// Testing the third array. |
| 180 | +for (inti =0;i <sorterObj3.array_length -1;i++) { |
| 181 | +assert ((sorterObj3.array[i] <=sorterObj3.array[i +1])) :"Array is not sorted"; |
212 | 182 | } |
| 183 | + } |
| 184 | + |
| 185 | +publicstaticvoidmain(String[]args) { |
| 186 | +test(); |
| 187 | + } |
213 | 188 | } |
