Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit66adafb

Browse files
* Add Tim Sort implementation in Java* Add comments and complete implementation of TimSort Algorithm* Add better docs* Add@brief's and test method* Fix errors* add Test method* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Add tests* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.java* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>* Update Sorts/TimSort.javaCo-authored-by: Ayaan Khan <ayaankhan98@gmail.com>Co-authored-by: Ayaan Khan <ayaankhan98@gmail.com>
1 parentd2d5efd commit66adafb

File tree

1 file changed

+213
-0
lines changed

1 file changed

+213
-0
lines changed

‎Sorts/TimSort.java‎

Lines changed: 213 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,213 @@
1+
packageSorts;
2+
3+
importjava.lang.Math;
4+
importjava.util.Random;
5+
6+
/**
7+
* @author [Hemanth Kotagiri](https://github.com/hemanth-kotagiri)
8+
* @see [Tim Sort](https://en.wikipedia.org/wiki/Tim_sort)
9+
*/
10+
11+
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;
24+
}
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+
}
42+
}
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;
51+
}
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+
}
68+
}
69+
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+
}
90+
}
91+
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+
}
138+
}
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();
166+
}
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();
177+
}
178+
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+
}
208+
}
209+
210+
publicstaticvoidmain(String[]args) {
211+
test();
212+
}
213+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp