[FEATURE REQUEST] QuickSort Algo for LinkedList

[Prabhat-Kumar-42]

What would you like to Propose?

Adding QuickSort Algorithm for Linked List

I was exploring the datastructures/list and sorts directory and noticed that there is no QuickSort Algorithm implemented for Linked Lists.

So far, I have found the following sorting algorithms:

1. Merge Sort for Linked List in the datastructures/list directory.

2. A source file named LinkListSort.java in the sorts/ directory, which sorts the linked list in three ways:

   • Insertion Sort
   • Merge Sort
   • Heap Sort

I propose adding the QuickSort Algorithm for Linked Lists to the datastructures/list directory.

Issue details

Implementation and How it Works :
Problem :
QuickSort on Linked List

Note: Taking head as pivot in current implementation.

 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   

Additional Information

No response

[Prabhat-Kumar-42]

Hello,
I have created a pull request regarding this.
Please take a look.
Let me know if there's any issue. I will solve it asap.
Hope this helps the community.
Thank You !! :)

[Prabhat-Kumar-42]

Solved and PR merged #4487