Quick Sort for Singly Linked List using Python

Quick Sort: It's basically works on divide and conquer method, choose pivot as first node,last ,middle and make partition and swap values.

 

First Check out Basic Operation on Singly Linked list.

Code:

class Node:

def __init__(self, data=None):

self.data = data

self.next = None

class LinkedList:

def __init__(self):

self.head = None

""" Quick Sort"""

# it's basically works on divide on conquer method

# in this function we'll swap values and return pivot

def partition(self, start, end):

pivot = start # taking start(first node) as pivot

cur = start

while (cur != None and cur != end):

if (cur.data < end.data):

pivot = start

start.data, cur.data = cur.data,start.data

start = start.next

cur = cur.next

start.data,end.data = end.data, start.data

return pivot

def quickSort(self, start, end):

#base case

if start == end:

return

#setting up pivot

pivot = self.partition(start, end)

# recursion

if (pivot != None and pivot.next != None):

self.quickSort(pivot.next, end)

if (pivot != None and start != pivot):

self.quickSort(start, pivot)

 

Time Complexity:

• Best: 𝛺(n*log n)
• Average:Θ(n*log n)
• Worst: O(n*n)

Tip: If we take take pivot wisely(random pivot would be great choice) then worst case can reduced to O(n*log n)

 Space Complexity: O(1)

Note: if You have any suggestion put in comments.

Thank You 😊😊

Other Sorting Algorithms:

• Bubble Sort for Singly Linked list
• Insertion Sort for Singly Linked list
• Merge Sort for Singly Linked list