You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
/** Program description - To sort the LinkList as per sorting technique */
6
+
7
+
packagecom.thealgorithms.sorts;
8
+
importjava.util.*;
9
+
publicclassLinkList_Sort {
10
+
publicstaticbooleanisSorted(intp[] ,intoption) {
11
+
try (Scannersc =newScanner(System.in)) {
12
+
}
13
+
inta[] =p;
14
+
// Array is taken as input from test class
15
+
intb[] =p;
16
+
// array similar to a
17
+
intch =option;
18
+
// Choice is choosed as any number from 1 to 3 (So the linked list will be sorted by Merge sort technique/Insertion sort technique/Heap sort technique)
19
+
switch (ch) {
20
+
case1:
21
+
Tasknm =newTask();
22
+
Nodestart =null,prev =null,fresh,ptr;
23
+
for (inti =0;i <a.length;i++) {
24
+
// New nodes are created and values are added
25
+
fresh =newNode();// Node class is called
26
+
fresh.val =a[i];// Node val is stored
27
+
if (start ==null)
28
+
start =fresh;
29
+
else
30
+
prev.next =fresh;
31
+
prev =fresh;
32
+
}
33
+
start =nm.sort_by_mergesort(start);
34
+
// method is being called
35
+
inti=0;
36
+
for (ptr =start;ptr !=null;ptr =ptr.next) {
37
+
a[i++]=ptr.val;
38
+
// storing the sorted values in the array
39
+
}
40
+
Arrays.sort(b);
41
+
// array b is sorted and it will return true when checked with sorted list
42
+
LinkList_Sortuu=newLinkList_Sort();
43
+
if(uu.compare(a,b))
44
+
{
45
+
returntrue;
46
+
}
47
+
else
48
+
{
49
+
returnfalse;
50
+
}
51
+
// The given array and the expected array is checked if both are same then true is displayed else false is displayed
52
+
case2:
53
+
Nodestart1 =null,prev1 =null,fresh1,ptr1;
54
+
for (inti1 =0;i1 <a.length;i1++) {
55
+
// New nodes are created and values are added
56
+
fresh1 =newNode();// New node is created
57
+
fresh1.val =a[i1];// Value is stored in the value part of the node
58
+
if (start1 ==null)
59
+
start1 =fresh1;
60
+
else
61
+
prev1.next =fresh1;
62
+
prev1 =fresh1;
63
+
}
64
+
Task1kk =newTask1();
65
+
start1 =kk.sort_by_insertionsort(start1);
66
+
// method is being called
67
+
inti1=0;
68
+
for (ptr1 =start1;ptr1 !=null;ptr1 =ptr1.next) {
69
+
a[i1++]=ptr1.val;
70
+
// storing the sorted values in the array
71
+
}
72
+
LinkList_Sortuu1=newLinkList_Sort();
73
+
// array b is not sorted and it will return false when checked with sorted list
74
+
if(uu1.compare(a,b))
75
+
{
76
+
returntrue;
77
+
}
78
+
else
79
+
{
80
+
returnfalse;
81
+
}
82
+
// The given array and the expected array is checked if both are same then true is displayed else false is displayed
83
+
case3:
84
+
Task2mm =newTask2();
85
+
Nodestart2 =null,prev2 =null,fresh2,ptr2;
86
+
for (inti2 =0;i2 <a.length;i2++) {
87
+
// New nodes are created and values are added
88
+
fresh2 =newNode();// Node class is created
89
+
fresh2.val =a[i2];// Value is stored in the value part of the Node
90
+
if (start2 ==null)
91
+
start2 =fresh2;
92
+
else
93
+
prev2.next =fresh2;
94
+
prev2 =fresh2;
95
+
}
96
+
start2 =mm.sort_by_heapsort(start2);
97
+
// method is being called
98
+
inti3=0;
99
+
for (ptr2 =start2;ptr2 !=null;ptr2 =ptr2.next) {
100
+
a[i3++]=ptr2.val;
101
+
// storing the sorted values in the array
102
+
}
103
+
Arrays.sort(b);
104
+
// array b is sorted and it will return true when checked with sorted list
105
+
LinkList_Sortuu2=newLinkList_Sort();
106
+
if(uu2.compare(a,b))
107
+
{
108
+
returntrue;
109
+
}
110
+
else
111
+
{
112
+
returnfalse;
113
+
}
114
+
// The given array and the expected array is checked if both are same then true is displayed else false is displayed
115
+
default:
116
+
// default is used incase user puts a unauthorized value
117
+
System.out.println("Wrong choice");
118
+
}
119
+
// Switch case is used to call the classes as per the user requirement
120
+
returnfalse;
121
+
}
122
+
booleancompare(inta[] ,intb[])
123
+
{
124
+
for(inti=0;i<a.length;i++)
125
+
{
126
+
if(a[i]!=b[i])
127
+
returnfalse;
128
+
}
129
+
returntrue;
130
+
// Both the arrays are checked for equalness. If both are equal then true is returned else false is returned
131
+
}
132
+
/**
133
+
* OUTPUT :
134
+
* Input - {89,56,98,123,26,75,12,40,39,68,91} is same for all the 3 classes
135
+
* Output: [12 26 39 40 56 68 75 89 91 98 123] is same for all the 3 classes
136
+
* 1st approach Time Complexity : O(n logn)
137
+
* Auxiliary Space Complexity : O(n)
138
+
* 2nd approach Time Complexity : O(n^2)
139
+
* Auxiliary Space Complexity : O(n)
140
+
* 3rd approach Time Complexity : O(n logn)
141
+
* Auxiliary Space Complexity : O(n)
142
+
*/
143
+
}
144
+
145
+
classNode {
146
+
intval;
147
+
Nodenext;
148
+
// Node class for creation of linklist nodes
149
+
}
150
+
151
+
classTask {
152
+
staticinta[];
153
+
154
+
publicNodesort_by_mergesort(Nodehead) {
155
+
if (head ==null ||head.next ==null)
156
+
returnhead;
157
+
intc =count(head);
158
+
a =newint[c];
159
+
// Array of size c is created
160
+
inti =0;
161
+
for (Nodeptr =head;ptr !=null;ptr =ptr.next) {
162
+
a[i++] =ptr.val;
163
+
}
164
+
// values are stored in the array
165
+
i =0;
166
+
task(a,0,c -1);
167
+
// task method will be executed
168
+
for (Nodeptr =head;ptr !=null;ptr =ptr.next) {
169
+
ptr.val =a[i++];
170
+
// Value is stored in the linklist after being sorted
171
+
}
172
+
returnhead;
173
+
}
174
+
175
+
intcount(Nodehead) {
176
+
intc =0;
177
+
Nodeptr;
178
+
for (ptr =head;ptr !=null;ptr =ptr.next) {
179
+
c++;
180
+
}
181
+
returnc;
182
+
// This Method is used to count number of elements/nodes present in the linklist
183
+
// It will return a integer type value denoting the number of nodes present
184
+
}
185
+
186
+
voidtask(intn[],inti,intj) {
187
+
if (i <j) {
188
+
intm = (i +j) /2;
189
+
task(n,i,m);
190
+
task(n,m +1,j);
191
+
task1(n,i,m,j);
192
+
// Array is halved and sent for sorting
193
+
}
194
+
}
195
+
196
+
voidtask1(intn[],ints,intm,inte) {
197
+
inti =s,k =0,j =m +1;
198
+
intb[] =newint[e -s +1];
199
+
while (i <=m &&j <=e) {
200
+
if (n[j] >=n[i])
201
+
b[k++] =n[i++];
202
+
else
203
+
b[k++] =n[j++];
204
+
}
205
+
// Smallest number is stored after checking from both the arrays
206
+
while (i <=m) {
207
+
b[k++] =n[i++];
208
+
}
209
+
while (j <=e) {
210
+
b[k++] =n[j++];
211
+
}
212
+
for (intp =s;p <=e;p++) {
213
+
a[p] =b[p -s];
214
+
}
215
+
}
216
+
// The method task and task1 is used to sort the linklist using merge sort
217
+
}
218
+
classTask1 {
219
+
publicNodesort_by_insertionsort(Nodehead) {
220
+
if (head ==null ||head.next ==null)
221
+
returnhead;
222
+
intc =count(head);
223
+
inta[] =newint[c];
224
+
// Array of size c is created
225
+
a[0] =head.val;
226
+
inti;
227
+
Nodeptr;
228
+
for (ptr =head.next,i =1;ptr !=null;ptr =ptr.next,i++) {
229
+
intj =i -1;
230
+
while (j >=0 &&a[j] >ptr.val) {
231
+
// values are stored in the array
232
+
a[j +1] =a[j];
233
+
j--;
234
+
}
235
+
a[j +1] =ptr.val;
236
+
}
237
+
i =0;
238
+
for (ptr =head;ptr !=null;ptr =ptr.next) {
239
+
ptr.val =a[i++];
240
+
// Value is stored in the linklist after being sorted
241
+
}
242
+
returnhead;
243
+
}
244
+
245
+
staticintcount(Nodehead) {
246
+
Nodeptr;
247
+
intc =0;
248
+
for (ptr =head;ptr !=null;ptr =ptr.next) {
249
+
c++;
250
+
}
251
+
returnc;
252
+
// This Method is used to count number of elements/nodes present in the linklist
253
+
// It will return a integer type value denoting the number of nodes present
254
+
}
255
+
// The method task and task1 is used to sort the linklist using insertion sort
256
+
}
257
+
258
+
classTask2 {
259
+
staticinta[];
260
+
261
+
publicNodesort_by_heapsort(Nodehead) {
262
+
if (head ==null ||head.next ==null)
263
+
returnhead;
264
+
intc =count(head);
265
+
a =newint[c];
266
+
// Array of size c is created
267
+
inti =0;
268
+
for (Nodeptr =head;ptr !=null;ptr =ptr.next) {
269
+
a[i++] =ptr.val;
270
+
// values are stored in the array
271
+
}
272
+
i =0;
273
+
task(a);
274
+
for (Nodeptr =head;ptr !=null;ptr =ptr.next) {
275
+
ptr.val =a[i++];
276
+
// Value is stored in the linklist after being sorted
277
+
}
278
+
returnhead;
279
+
}
280
+
281
+
intcount(Nodehead) {
282
+
intc =0;
283
+
Nodeptr;
284
+
for (ptr =head;ptr !=null;ptr =ptr.next) {
285
+
c++;
286
+
}
287
+
returnc;
288
+
// This Method is used to count number of elements/nodes present in the linklist
289
+
// It will return a integer type value denoting the number of nodes present
290
+
}
291
+
292
+
voidtask(intn[]) {
293
+
intk =n.length;
294
+
for (inti =k /2 -1;i >=0;i--) {
295
+
task1(n,k,i);
296
+
}
297
+
for (inti =k -1;i >0;i--) {
298
+
intd =n[0];
299
+
n[0] =n[i];
300
+
n[i] =d;
301
+
task1(n,i,0);
302
+
// recursive calling of task1 method
303
+
}
304
+
}
305
+
306
+
voidtask1(intn[],intk,inti) {
307
+
intp =i;
308
+
intl =2 *i +1;
309
+
intr =2 *i +2;
310
+
if (l <k &&n[l] >n[p])
311
+
p =l;
312
+
if (r <k &&n[r] >n[p])
313
+
p =r;
314
+
if (p !=i) {
315
+
intd =n[p];
316
+
n[p] =n[i];
317
+
n[i] =d;
318
+
task1(n,k,p);
319
+
}
320
+
}
321
+
// The method task and task1 is used to sort the linklist using heap sort