Repository: TheAlgorithms/Java
Pull request #4487 (2023-10-01 08:55:06)

[FEATURE] #4486  QuickSort Algo for LinkedList
Description : 
   - Added QuickSort Algorithm for Linked List.
   - Provided a detailed documentation in source-code file 

<!-- 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 it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.


Prabhat-Kumar-42: # QuickSort Feature Added for Linked List

Hey,

I added the QuickSort feature for linked lists. Please review it.

Although I have checked it for various test cases, if any issue arises, please let me know, and I will resolve it as soon as possible.

Thank you! 😊
Prabhat-Kumar-42: > Why did you add three files, and should that file remove the main method, also added test cases.

Yes, thank you for notifying me about the extra files. I really appreciate it. These are the files from other PRs I made in this repo.
I accidentally created the new feature branch from the previous working feature branch, instead of the master branch.
I removed the extra files.
Also, the main method is just for test cases, it can be safely removed, but I just left it there in case someone wanted to test the source code.

If there's anything else, please let me know.

BamaCharanChhandogi: Hello, please review the other LinkedList files to understand how to add different test case files. After adding test cases, you should remove the `main` method, as it is not needed.

Secondly, there is no need to create a `LinkedList class`. You are importing a package, so you can use it without declaring a `node` class.
Prabhat-Kumar-42: > Hello, please review the other LinkedList files to understand how to add different test case files. After adding test cases, you should remove the `main` method, as it is not needed.
> 
> Secondly, there is no need to create a `LinkedList class`. You are importing a package, so you can use it without declaring a `node` class.

Got it, Thank you for the review. Currently Working on the issues you mentioned.

Prabhat-Kumar-42: @BamaCharanChhandogi 
Please review the code.
Ignore the main method as it will be removed after building the test file.
If everything's alright with it then I will move to the build the test file.
Thank You !!
Prabhat-Kumar-42: @BamaCharanChhandogi 
Just a quick follow-up.
I have resolved the issues about extra-files, main method and added test code as you mentioned.
Please review the progress.
Let me know if something needs to be added.

Thank You !!
BamaCharanChhandogi: Looks good
Prabhat-Kumar-42: > Looks good

Thank You for the review.
This is if first time contributing to open-source. I hope I am doing alright and thank you for guiding me through this contribution @BamaCharanChhandogi.
If everything with the code seems fine to you, I would like to merge my PR.
I would humbly request the maintainer(s) to please merge my request using the "hacktoberfest-accepted" label.
That would be helpful to me.
Thank You !!
 

Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/lists/QuickSortLinkedList.java b/src/main/java/com/thealgorithms/datastructures/lists/QuickSortLinkedList.java
new file mode 100644
index 00000000..36b6e9c6
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/lists/QuickSortLinkedList.java
@@ -0,0 +1,170 @@
+package com.thealgorithms.datastructures.lists;
+/*
+ *
+ * @aurthor - Prabhat-Kumar-42
+ * @github - https://github.com/Prabhat-Kumar-42
+ *
+ * Problem :
+ *    QuickSort on Linked List
+ *
+ * Note: Taking head as pivot in current implementation.
+ *        N represents NULL node
+ *    Example:
+ *
+ *      -> Given Linked List :
+ *            5 -> 3 -> 8 -> 1 -> 10 -> 2 -> 7 -> 4 -> 9 -> 6
+ *
+ *      -> How Sorting will work according to the QuickSort Algo written below
+ *
+ *      current pivot : 5
+ *      List lessThanPivot : 3 -> 1 -> 2 -> 4
+ *      List greaterThanPivot : 5 -> 8 -> 10 -> 7 -> 9 -> 6
+ *
+ *      -> reccur for lessThanPivot and greaterThanPivot
+ *
+ *            lessThanPivot :
+ *                current pivot : 3
+ *                lessThanPivot : 1 -> 2
+ *                greaterThanPivot : 4
+ *
+ *             greaterThanPivot:
+ *                 current pivot : 5
+ *                 lessThanPivot : null
+ *                 greaterThanPivot : 8 -> 10 -> 7 -> 9 -> 6
+ *
+ *        By following the above pattern, reccuring tree will form like below :
+ *
+ *        List-> 5 -> 3 -> 8 -> 1 -> 10 -> 2 -> 7 -> 4 -> 9 -> 6
+ *
+ *        Pivot :                  5
+ *                                /\
+ *                               /  \
+ *                              /    \
+ *                             /      \
+ *                            /        \
+ *        List: (3 -> 1 -> 2 -> 4)   (5 -> 8 -> 10 -> 7 -> 9 -> 6)
+ *        Pivot :          3               5
+ *                        /\              /\
+ *                       /  \            /  \
+ *                      /    \          /    \
+ *                     /      \        /      \
+ *         List:   (1 -> 2)   (4)   (N)   (8 -> 10 -> 7 -> 9 -> 6)
+ *         Pivot:     1        4                8
+ *                   /\       /\               /\
+ *                  /  \     /  \             /  \
+ *                 /    \   /    \           /    \
+ *         List:  (N)  (2) (N)   (N)   (6 -> 7)   (9 -> 10)
+ *         Pivot:       2                  6         9
+ *                     /\                 /\        /\
+ *                    /  \               /  \      /  \
+ *                   /    \             /    \    /    \
+ *         List:   (N)   (N)          (N)   (7) (N)   (10)
+ *         Pivot:                            7          10
+ *                                          /\          /\
+ *                                         /  \        /  \
+ *                                        /    \      /    \
+ *                                       (N)   (N)   (N)   (N)
+ *
+ *
+ *      -> After this the tree will reccur back (or backtrack)
+ *         and the returning list from left and right subtree will attach
+ *         themselves around pivot.
+ *         i.e. ,
+ *                  (listFromLeftSubTree) -> (Pivot) -> (listFromRightSubtree)
+ *
+ *         This will continue until whole list is merged back
+ *
+ *          eg :
+ *             Megring the above Tree back we get :
+ *
+ *          List: (1 -> 2)        (4)           (6 -> 7)         (9 -> 10)
+ *                  \             /                  \             /
+ *                   \           /                    \           /
+ *                    \         /                      \         /
+ *                     \       /                        \       /
+ *                      \     /                          \     /
+ *                       \   /                            \   /
+ *                        \ /                              \ /
+ *          Pivot:         3                                8
+ *          List:   (1 -> 2 -> 3 -> 4)            (6 -> 7 -> 8 -> 9 -> 10)
+ *                                  \              /
+ *                                   \            /
+ *                                    \          /
+ *                                     \        /
+ *                                      \      /
+ *                                       \    /
+ *                                        \  /
+ *                                         \/
+ *          Pivot:                          5
+ *          List:      (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10)
+ *
+ *
+ *      -> This will result in a sorted Linked List
+ */
+
+public class QuickSortLinkedList {
+
+    private SinglyLinkedList list = null; // Linked list
+    private Node head = null; // head of the list
+    // Counstructor
+    public QuickSortLinkedList(SinglyLinkedList list) {
+        this.list = list;
+        this.head = list.getHead();
+    }
+
+    // Function to sort a linked list using the Quick Sort algorithm
+    public void sortList() {
+        head = sortList(head);
+        list.setHead(head);
+    }
+    // helper function to apply QuickSort to the stored list
+    public Node sortList(Node head) {
+        if (head == null || head.next == null) {
+            return head;
+        }
+
+        // Choose the first element as the pivot
+        Node pivot = head;
+        head = head.next;
+        pivot.next = null;
+
+        Node lessHead = new Node(); // stores the nodes cantaining data less than pivot node
+        Node lessTail = lessHead; // tail of lessHead
+        Node greaterHead = new Node(); // stores the nodes cantaining data greater than pivot node
+        Node greaterTail = greaterHead; // tail of greaterHead
+
+        // Partition the list around the pivot
+        while (head != null) {
+            if (head.value < pivot.value) {
+                lessTail.next = head;
+                lessTail = lessTail.next;
+            } else {
+                greaterTail.next = head;
+                greaterTail = greaterTail.next;
+            }
+            head = head.next;
+        }
+
+        // Seperating lessHead and greaterHead to form two seperate linkedList
+        lessTail.next = null;
+        greaterTail.next = null;
+
+        // Recursively sort the sublists
+        Node sortedLess = sortList(lessHead.next);
+        Node sortedGreater = sortList(greaterHead.next);
+
+        // Combine the sorted sublists and pivot
+        if (sortedLess == null) {
+            pivot.next = sortedGreater;
+            return pivot;
+        } else {
+            Node current = sortedLess;
+            while (current.next != null) {
+                current = current.next;
+            }
+            current.next = pivot;
+            pivot.next = sortedGreater;
+            return sortedLess;
+        }
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/lists/QuickSortLinkedListTest.java b/src/test/java/com/thealgorithms/datastructures/lists/QuickSortLinkedListTest.java
new file mode 100644
index 00000000..f4bcfd7f
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/lists/QuickSortLinkedListTest.java
@@ -0,0 +1,66 @@
+package com.thealgorithms.datastructures.lists;
+
+/**
+ * Test cases for QuickSortLinkedList
+ * Author: Prabhat-Kumar-42
+ * GitHub: https://github.com/Prabhat-Kumar-42
+ */
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+public class QuickSortLinkedListTest {
+
+    @Test
+    public void testSortEmptyList() {
+        SinglyLinkedList emptyList = new SinglyLinkedList();
+        QuickSortLinkedList sorter = new QuickSortLinkedList(emptyList);
+
+        // Test case: Sorting an empty list should result in an empty list
+        sorter.sortList();
+        assertNull(emptyList.getHead());
+    }
+
+    @Test
+    public void testSortSingleNodeList() {
+        SinglyLinkedList singleNodeList = new SinglyLinkedList();
+        singleNodeList.insert(5);
+        QuickSortLinkedList sorter = new QuickSortLinkedList(singleNodeList);
+
+        // Test case: Sorting a list with a single node should result in the same list
+        sorter.sortList();
+        assertEquals(5, singleNodeList.getHead().value);
+        assertNull(singleNodeList.getHead().next);
+    }
+
+    @Test
+    public void testSortMultipleElementsList() {
+        SinglyLinkedList list = new SinglyLinkedList();
+        list.insert(5);
+        list.insert(3);
+        list.insert(8);
+        list.insert(1);
+        list.insert(10);
+        list.insert(2);
+        list.insert(7);
+        list.insert(4);
+        list.insert(9);
+        list.insert(6);
+        QuickSortLinkedList sorter = new QuickSortLinkedList(list);
+
+        // Test case: Sorting a list with multiple elements
+        sorter.sortList();
+        assertEquals(1, list.getHead().value);
+        assertEquals(2, list.getHead().next.value);
+        assertEquals(3, list.getHead().next.next.value);
+        assertEquals(4, list.getHead().next.next.next.value);
+        assertEquals(5, list.getHead().next.next.next.next.value);
+        assertEquals(6, list.getHead().next.next.next.next.next.value);
+        assertEquals(7, list.getHead().next.next.next.next.next.next.value);
+        assertEquals(8, list.getHead().next.next.next.next.next.next.next.value);
+        assertEquals(9, list.getHead().next.next.next.next.next.next.next.next.value);
+        assertEquals(10, list.getHead().next.next.next.next.next.next.next.next.next.value);
+        assertNull(list.getHead().next.next.next.next.next.next.next.next.next.next);
+    }
+}