Quick Sort on Linked List

Last updated: 29th Aug, 2020

Problem Statment

Sort the given Linked List using Quick Sort. Input:
A method takes 1 argument: address of the head of the linked list. The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list. There are multiple test cases. For each test case, this method will be called individually. Output:
Set *link to head of resultant linked list. Input Format
[10 -> 7 -> 11-> 12-> 6]

Output Format
[ 6 -> 7 -> 10-> 11-> 12]

Approach:

1. A temporary variable Pivot will store the element of the very first node
2. Traverse the loop through the list and store the values to the **left side** of the pivot value which are less than pivot
3. Store the values to the right side of the pivot value which are greater than pivot
4. Now the value of pivot is located to it desired position
5. Store the value of the pivot
6. Now, sort the elements before the pivot value and after the pivot value in the same manner as done before by calling the functions.
7. Finally print the sorted list

Python Code


# check if the list contains 1 or more nodes
def getLink(head):
  temp = head
  while temp is not None and temp.next is not None:
    temp = temp.next
  return temp
                        
#initialize the pivot ,newHead and newLink to the partition function
def quickSortRec(head, link):
  if head is None or head == link:
    return head
  newHead = None 
  newLink = None
  pivot, newHead, newLink = partition(head, link, newHead, newLink)
  if newHead != pivot:
    temp = newHead
    while temp.next != pivot:
      temp = temp.next
    temp.next = None
    newHead = quickSortRec(newHead, temp)
    temp = getLink(newHead)
    temp.next = pivot
  pivot.next = quickSortRec(pivot.next, newLink)  
  return newHead
#divide the entire list into two parts
#where the left of the pivot value will have the values less than pivot
# and right of the pivot value will have the vlaues greater than pivot 
def partition(head, Link, newHead, newLink):
  pivot = Link
  prev = None
  curr = head
  end = pivot
  while curr is not pivot:
    if curr.data < pivot.data:
      if newHead is None:
        newHead = curr
      prev = curr
      curr = curr.next
    else:
      if prev:
        prev.next = curr.next
      temp = curr.next
      curr.next = None
      end.next = curr
      end = curr
      curr = temp
  if newHead is None:
    newHead = pivot
  newLink = end
  return pivot, newHead, newLink
                        
  #Driver's code
                        
  from collections import defaultdict
  class Node:
    def __init__(self,data):
      self.data=data
      self.next=None
                        
  class Llist:
    def __init__(self):
      self.head=None
                            
    def insert(self,data,tail):
      node=Node(data)
                                
      if not self.head:
        self.head=node
        return node
                                
      tail.next=node
      return node
                                
    def nodeID(head,dic):
      while head:
        dic[head.data].append(id(head))
        head=head.next
                                
                        
                        
    def printList(head,dic):
      while head:
        if id(head) not in dic[head.data]:
          print("Do'nt swap data, swap pointer/node")
          return
        print(head.data,end=' ')
        head=head.next
                                
    if __name__ == '__main__':
      t=int(input())
                            
      for i in range(t):
        n=int(input())
                                
        arr=[int(x) for x in input().split()]
                                
        ll=Llist()
        tail=None
                                
        for nodeData in arr:
          tail=ll.insert(nodeData,tail)
                                    
        dic=defaultdict(list) # dictonary to keep data and id of node
        nodeID(ll.head,dic)   # putting data and its id
                                
        resHead=quickSortRec(ll.head)
        printList(resHead,dic)  #verifying and printing
        print()