Repository: TheAlgorithms/Java
Pull request #2882 (2021-12-20 05:14:05)

Added sort list Algorithm
### **Describe your change:**

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

<!-- Add any reference to previous pull-request or issue -->

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.


siddhant2002: @siriak Please check the updated pr
siddhant2002: @siriak Please check the updated pr
zhrgithub: ok


| |
张泓锐
|
|
***@***.***
|
签名由网易邮箱大师定制


在2022年01月19日 12:28，Siddhant Swarup ***@***.***> 写道：

@siriak Please check the updated pr

—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications on the go with GitHub Mobile for iOS or Android.
You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/LinkList_Sort.java b/src/main/java/com/thealgorithms/sorts/LinkList_Sort.java
new file mode 100644
index 00000000..24800916
--- /dev/null
+++ b/src/main/java/com/thealgorithms/sorts/LinkList_Sort.java
@@ -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
+}
\ No newline at end of file


Test patch:
diff --git a/src/test/java/com/thealgorithms/others/LinkList_Sort_test.java b/src/test/java/com/thealgorithms/others/LinkList_Sort_test.java
new file mode 100644
index 00000000..758d2532
--- /dev/null
+++ b/src/test/java/com/thealgorithms/others/LinkList_Sort_test.java
@@ -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));
+	}
+}