TheAlgorithms · siriak · Jan 19, 2022 · Dec 5, 2021 · Dec 7, 2021 · Dec 8, 2021
@@ -0,0 +1,322 @@
+/** Author : Siddhant Swarup Mallick
+ * Github : https://github.com/siddhant2002
+ */
+
+/** Program description - To sort the LinkList as per sorting technique */
+
+package com.thealgorithms.sorts;
+import java.util.*;
+public class LinkList_Sort {
+    public static boolean isSorted(int p[] , int option) {
+        try (Scanner sc = new Scanner(System.in)) {
+        }
+        int a[] = p;
+        // Array is taken as input from test class
+        int b[] = p;
+        // array similar to a
+        int ch = option;
+        // 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)
+        switch (ch) {
+            case 1:
+                Task nm = new Task();
+                Node start = null, prev = null, fresh, ptr;
+                for (int i = 0; i < a.length; i++) {
+                    // New nodes are created and values are added
+                    fresh = new Node(); // Node class is called
+                    fresh.val = a[i]; // Node val is stored
+                    if (start == null)
+                        start = fresh;
+                    else
+                        prev.next = fresh;
+                    prev = fresh;
+                }
+                start = nm.sort_by_mergesort(start);
+                // method is being called
+                int i=0;
+                for (ptr = start;ptr != null; ptr = ptr.next) {
+                    a[i++]=ptr.val;
+                    // storing the sorted values in the array
+                }
+                Arrays.sort(b);
+                // array b is sorted and it will return true when checked with sorted list
+                LinkList_Sort uu=new LinkList_Sort();
+                if(uu.compare(a,b))
+                {
+                    return true;
+                }
+                else
+                {
+                    return false;
+                }
+                // The given array and the expected array is checked if both are same then true is displayed else false is displayed
+            case 2:
+                Node start1 = null, prev1 = null, fresh1, ptr1;
+                for (int i1 = 0; i1 < a.length; i1++) {
+                    // New nodes are created and values are added
+                    fresh1 = new Node(); // New node is created
+                    fresh1.val = a[i1]; // Value is stored in the value part of the node
+                    if (start1 == null)
+                        start1 = fresh1;
+                    else
+                        prev1.next = fresh1;
+                    prev1 = fresh1;
+                }
+                Task1 kk = new Task1();
+                start1 = kk.sort_by_insertionsort(start1);
+                // method is being called
+                int i1=0;
+                for (ptr1 = start1; ptr1 != null; ptr1 = ptr1.next) {
+                    a[i1++]=ptr1.val;
+                    // storing the sorted values in the array
+                }
+                LinkList_Sort uu1=new LinkList_Sort();
+                // array b is not sorted and it will return false when checked with sorted list
+                if(uu1.compare(a,b))
+                {
+                    return true;
+                }
+                else
+                {
+                    return false;
+                }
+                // The given array and the expected array is checked if both are same then true is displayed else false is displayed
+            case 3:
+                Task2 mm = new Task2();
+                Node start2 = null, prev2 = null, fresh2, ptr2;
+                for (int i2 = 0; i2 < a.length; i2++) {
+                    // New nodes are created and values are added
+                    fresh2 = new Node(); // Node class is created
+                    fresh2.val = a[i2]; // Value is stored in the value part of the Node
+                    if (start2 == null)
+                        start2 = fresh2;
+                    else
+                        prev2.next = fresh2;
+                    prev2 = fresh2;
+                }
+                start2 = mm.sort_by_heapsort(start2);
+                // method is being called
+                int i3=0;
+                for (ptr2 = start2; ptr2 != null; ptr2 = ptr2.next) {
+                    a[i3++]=ptr2.val;
+                    // storing the sorted values in the array
+                }
+                Arrays.sort(b);
+                // array b is sorted and it will return true when checked with sorted list
+                LinkList_Sort uu2=new LinkList_Sort();
+                if(uu2.compare(a,b))
+                {
+                    return true;
+                }
+                else
+                {
+                    return false;
+                }
+                // The given array and the expected array is checked if both are same then true is displayed else false is displayed
+            default:
+                // default is used incase user puts a unauthorized value
+                System.out.println("Wrong choice");
+        }
+        // Switch case is used to call the classes as per the user requirement
+        return false;
+    }
+    boolean compare(int a[] , int b[])
+    {
+        for(int i=0;i<a.length;i++)
+        {
+            if(a[i]!=b[i])
+            return false;
+        }
+        return true;
+        // Both the arrays are checked for equalness. If both are equal then true is returned else false is returned
+    }
+    /**
+     * OUTPUT :
+     * Input - {89,56,98,123,26,75,12,40,39,68,91} is same for all the 3 classes
+     * Output: [12 26 39 40 56 68 75 89 91 98 123] is same for all the 3 classes
+     * 1st approach Time Complexity : O(n logn)
+     * Auxiliary Space Complexity : O(n)
+     * 2nd approach Time Complexity : O(n^2)
+     * Auxiliary Space Complexity : O(n)
+     * 3rd approach Time Complexity : O(n logn)
+     * Auxiliary Space Complexity : O(n)
+     */
+}
+
+class Node {
+    int val;
+    Node next;
+    // Node class for creation of linklist nodes
+}
+
+class Task {
+    static int a[];
+
+    public Node sort_by_mergesort(Node head) {
+        if (head == null || head.next == null)
+            return head;
+        int c = count(head);
+        a = new int[c];
+        // Array of size c is created
+        int i = 0;
+        for (Node ptr = head; ptr != null; ptr = ptr.next) {
+            a[i++] = ptr.val;
+        }
+        // values are stored in the array
+        i = 0;
+        task(a, 0, c - 1);
+        // task method will be executed
+        for (Node ptr = head; ptr != null; ptr = ptr.next) {
+            ptr.val = a[i++];
+            // Value is stored in the linklist after being sorted
+        }
+        return head;
+    }
+
+    int count(Node head) {
+        int c = 0;
+        Node ptr;
+        for (ptr = head; ptr != null; ptr = ptr.next) {
+            c++;
+        }
+        return c;
+        // This Method is used to count number of elements/nodes present in the linklist
+        // It will return a integer type value denoting the number of nodes present
+    }
+
+    void task(int n[], int i, int j) {
+        if (i < j) {
+            int m = (i + j) / 2;
+            task(n, i, m);
+            task(n, m + 1, j);
+            task1(n, i, m, j);
+            // Array is halved and sent for sorting
+        }
+    }
+
+    void task1(int n[], int s, int m, int e) {
+        int i = s, k = 0, j = m + 1;
+        int b[] = new int[e - s + 1];
+        while (i <= m && j <= e) {
+            if (n[j] >= n[i])
+                b[k++] = n[i++];
+            else
+                b[k++] = n[j++];
+        }
+        // Smallest number is stored after checking from both the arrays
+        while (i <= m) {
+            b[k++] = n[i++];
+        }
+        while (j <= e) {
+            b[k++] = n[j++];
+        }
+        for (int p = s; p <= e; p++) {
+            a[p] = b[p - s];
+        }
+    }
+    // The method task and task1 is used to sort the linklist using merge sort
+}
+class Task1 {
+    public Node sort_by_insertionsort(Node head) {
+        if (head == null || head.next == null)
+            return head;
+        int c = count(head);
+        int a[] = new int[c];
+        // Array of size c is created
+        a[0] = head.val;
+        int i;
+        Node ptr;
+        for (ptr = head.next, i = 1; ptr != null; ptr = ptr.next, i++) {
+            int j = i - 1;
+            while (j >= 0 && a[j] > ptr.val) {
+                // values are stored in the array
+                a[j + 1] = a[j];
+                j--;
+            }
+            a[j + 1] = ptr.val;
+        }
+        i = 0;
+        for (ptr = head; ptr != null; ptr = ptr.next) {
+            ptr.val = a[i++];
+            // Value is stored in the linklist after being sorted
+        }
+        return head;
+    }
+
+    static int count(Node head) {
+        Node ptr;
+        int c = 0;
+        for (ptr = head; ptr != null; ptr = ptr.next) {
+            c++;
+        }
+        return c;
+        // This Method is used to count number of elements/nodes present in the linklist
+        // It will return a integer type value denoting the number of nodes present
+    }
+    // The method task and task1 is used to sort the linklist using insertion sort
+}
+
+class Task2 {
+    static int a[];
+
+    public Node sort_by_heapsort(Node head) {
+        if (head == null || head.next == null)
+            return head;
+        int c = count(head);
+        a = new int[c];
+        // Array of size c is created
+        int i = 0;
+        for (Node ptr = head; ptr != null; ptr = ptr.next) {
+            a[i++] = ptr.val;
+            // values are stored in the array
+        }
+        i = 0;
+        task(a);
+        for (Node ptr = head; ptr != null; ptr = ptr.next) {
+            ptr.val = a[i++];
+            // Value is stored in the linklist after being sorted
+        }
+        return head;
+    }
+
+    int count(Node head) {
+        int c = 0;
+        Node ptr;
+        for (ptr = head; ptr != null; ptr = ptr.next) {
+            c++;
+        }
+        return c;
+        // This Method is used to count number of elements/nodes present in the linklist
+        // It will return a integer type value denoting the number of nodes present
+    }
+
+    void task(int n[]) {
+        int k = n.length;
+        for (int i = k / 2 - 1; i >= 0; i--) {
+            task1(n, k, i);
+        }
+        for (int i = k - 1; i > 0; i--) {
+            int d = n[0];
+            n[0] = n[i];
+            n[i] = d;
+            task1(n, i, 0);
+            // recursive calling of task1 method
+        }
+    }
+
+    void task1(int n[], int k, int i) {
+        int p = i;
+        int l = 2 * i + 1;
+        int r = 2 * i + 2;
+        if (l < k && n[l] > n[p])
+            p = l;
+        if (r < k && n[r] > n[p])
+            p = r;
+        if (p != i) {
+            int d = n[p];
+            n[p] = n[i];
+            n[i] = d;
+            task1(n, k, p);
+        }
+    }
+    // The method task and task1 is used to sort the linklist using heap sort
+}
@@ -0,0 +1,64 @@
+package com.thealgorithms.others;
+import org.junit.jupiter.api.Test;
+
+import com.thealgorithms.sorts.LinkList_Sort;
+
+import static org.junit.jupiter.api.Assertions.*;
+public class LinkList_Sort_test {
+    @Test
+	void testForOneElement() 
+	{
+        int a[]={56};
+		assertTrue(LinkList_Sort.isSorted(a,2));
+	}
+
+	@Test
+	void testForTwoElements() 
+	{
+        int a[]={6,4};
+		assertTrue(LinkList_Sort.isSorted(a,1));
+	}
+
+	@Test
+	void testForThreeElements() 
+	{
+		int a[]={875,253,12};
+		assertTrue(LinkList_Sort.isSorted(a,3));
+	}
+
+	@Test
+	void testForFourElements() 
+	{
+		int a[]={86,32,87,13};
+		assertFalse(LinkList_Sort.isSorted(a,2));
+	}
+
+	@Test
+	void testForFiveElements() 
+	{
+		int a[]={6,5,3,0,9};
+		assertTrue(LinkList_Sort.isSorted(a,1));
+	}
+
+
+	@Test
+	void testForSixElements() 
+	{
+		int a[]={9,65,432,32,47,327};
+		assertTrue(LinkList_Sort.isSorted(a,3));
+	}
+
+	@Test
+	void testForSevenElements() 
+	{
+		int a[]={6,4,2,1,3,6,7};
+		assertTrue(LinkList_Sort.isSorted(a,1));
+    }
+
+	@Test
+	void testForEightElements() 
+	{
+		int a[]={123,234,145,764,322,367,768,34};
+		assertFalse(LinkList_Sort.isSorted(a,2));
+	}
+}