Skip to content

Commit 857c4aa

Browse files
siddhant2002siriak
siddhant2002
and
siriak
authored
Add linked list sorting (TheAlgorithms#2882)
Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parent 76fbe7c commit 857c4aa

File tree

2 files changed

+386
-0
lines changed

2 files changed

+386
-0
lines changed

‎src/main/java/com/thealgorithms/sorts/LinkList_Sort.java

Lines changed: 322 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,322 @@
1+
/** Author : Siddhant Swarup Mallick
2+
* Github : https://github.com/siddhant2002
3+
*/
4+
5+
/** Program description - To sort the LinkList as per sorting technique */
6+
7+
package com.thealgorithms.sorts;
8+
import java.util.*;
9+
public class LinkList_Sort {
10+
public static boolean isSorted(int p[] , int option) {
11+
try (Scanner sc = new Scanner(System.in)) {
12+
}
13+
int a[] = p;
14+
// Array is taken as input from test class
15+
int b[] = p;
16+
// array similar to a
17+
int ch = 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+
case 1:
21+
Task nm = new Task();
22+
Node start = null, prev = null, fresh, ptr;
23+
for (int i = 0; i < a.length; i++) {
24+
// New nodes are created and values are added
25+
fresh = new Node(); // 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+
int i=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_Sort uu=new LinkList_Sort();
43+
if(uu.compare(a,b))
44+
{
45+
return true;
46+
}
47+
else
48+
{
49+
return false;
50+
}
51+
// The given array and the expected array is checked if both are same then true is displayed else false is displayed
52+
case 2:
53+
Node start1 = null, prev1 = null, fresh1, ptr1;
54+
for (int i1 = 0; i1 < a.length; i1++) {
55+
// New nodes are created and values are added
56+
fresh1 = new Node(); // 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+
Task1 kk = new Task1();
65+
start1 = kk.sort_by_insertionsort(start1);
66+
// method is being called
67+
int i1=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_Sort uu1=new LinkList_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+
return true;
77+
}
78+
else
79+
{
80+
return false;
81+
}
82+
// The given array and the expected array is checked if both are same then true is displayed else false is displayed
83+
case 3:
84+
Task2 mm = new Task2();
85+
Node start2 = null, prev2 = null, fresh2, ptr2;
86+
for (int i2 = 0; i2 < a.length; i2++) {
87+
// New nodes are created and values are added
88+
fresh2 = new Node(); // 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+
int i3=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_Sort uu2=new LinkList_Sort();
106+
if(uu2.compare(a,b))
107+
{
108+
return true;
109+
}
110+
else
111+
{
112+
return false;
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+
return false;
121+
}
122+
boolean compare(int a[] , int b[])
123+
{
124+
for(int i=0;i<a.length;i++)
125+
{
126+
if(a[i]!=b[i])
127+
return false;
128+
}
129+
return true;
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+
class Node {
146+
int val;
147+
Node next;
148+
// Node class for creation of linklist nodes
149+
}
150+
151+
class Task {
152+
static int a[];
153+
154+
public Node sort_by_mergesort(Node head) {
155+
if (head == null || head.next == null)
156+
return head;
157+
int c = count(head);
158+
a = new int[c];
159+
// Array of size c is created
160+
int i = 0;
161+
for (Node ptr = 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 (Node ptr = head; ptr != null; ptr = ptr.next) {
169+
ptr.val = a[i++];
170+
// Value is stored in the linklist after being sorted
171+
}
172+
return head;
173+
}
174+
175+
int count(Node head) {
176+
int c = 0;
177+
Node ptr;
178+
for (ptr = head; ptr != null; ptr = ptr.next) {
179+
c++;
180+
}
181+
return c;
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+
void task(int n[], int i, int j) {
187+
if (i < j) {
188+
int m = (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+
void task1(int n[], int s, int m, int e) {
197+
int i = s, k = 0, j = m + 1;
198+
int b[] = new int[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 (int p = 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+
class Task1 {
219+
public Node sort_by_insertionsort(Node head) {
220+
if (head == null || head.next == null)
221+
return head;
222+
int c = count(head);
223+
int a[] = new int[c];
224+
// Array of size c is created
225+
a[0] = head.val;
226+
int i;
227+
Node ptr;
228+
for (ptr = head.next, i = 1; ptr != null; ptr = ptr.next, i++) {
229+
int j = 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+
return head;
243+
}
244+
245+
static int count(Node head) {
246+
Node ptr;
247+
int c = 0;
248+
for (ptr = head; ptr != null; ptr = ptr.next) {
249+
c++;
250+
}
251+
return c;
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+
class Task2 {
259+
static int a[];
260+
261+
public Node sort_by_heapsort(Node head) {
262+
if (head == null || head.next == null)
263+
return head;
264+
int c = count(head);
265+
a = new int[c];
266+
// Array of size c is created
267+
int i = 0;
268+
for (Node ptr = 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 (Node ptr = head; ptr != null; ptr = ptr.next) {
275+
ptr.val = a[i++];
276+
// Value is stored in the linklist after being sorted
277+
}
278+
return head;
279+
}
280+
281+
int count(Node head) {
282+
int c = 0;
283+
Node ptr;
284+
for (ptr = head; ptr != null; ptr = ptr.next) {
285+
c++;
286+
}
287+
return c;
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+
void task(int n[]) {
293+
int k = n.length;
294+
for (int i = k / 2 - 1; i >= 0; i--) {
295+
task1(n, k, i);
296+
}
297+
for (int i = k - 1; i > 0; i--) {
298+
int d = 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+
void task1(int n[], int k, int i) {
307+
int p = i;
308+
int l = 2 * i + 1;
309+
int r = 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+
int d = 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
322+
}

‎src/test/java/com/thealgorithms/others/LinkList_Sort_test.java

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.thealgorithms.others;
2+
import org.junit.jupiter.api.Test;
3+
4+
import com.thealgorithms.sorts.LinkList_Sort;
5+
6+
import static org.junit.jupiter.api.Assertions.*;
7+
public class LinkList_Sort_test {
8+
@Test
9+
void testForOneElement()
10+
{
11+
int a[]={56};
12+
assertTrue(LinkList_Sort.isSorted(a,2));
13+
}
14+
15+
@Test
16+
void testForTwoElements()
17+
{
18+
int a[]={6,4};
19+
assertTrue(LinkList_Sort.isSorted(a,1));
20+
}
21+
22+
@Test
23+
void testForThreeElements()
24+
{
25+
int a[]={875,253,12};
26+
assertTrue(LinkList_Sort.isSorted(a,3));
27+
}
28+
29+
@Test
30+
void testForFourElements()
31+
{
32+
int a[]={86,32,87,13};
33+
assertFalse(LinkList_Sort.isSorted(a,2));
34+
}
35+
36+
@Test
37+
void testForFiveElements()
38+
{
39+
int a[]={6,5,3,0,9};
40+
assertTrue(LinkList_Sort.isSorted(a,1));
41+
}
42+
43+
44+
@Test
45+
void testForSixElements()
46+
{
47+
int a[]={9,65,432,32,47,327};
48+
assertTrue(LinkList_Sort.isSorted(a,3));
49+
}
50+
51+
@Test
52+
void testForSevenElements()
53+
{
54+
int a[]={6,4,2,1,3,6,7};
55+
assertTrue(LinkList_Sort.isSorted(a,1));
56+
}
57+
58+
@Test
59+
void testForEightElements()
60+
{
61+
int a[]={123,234,145,764,322,367,768,34};
62+
assertFalse(LinkList_Sort.isSorted(a,2));
63+
}
64+
}

0 commit comments

Comments
 (0)