I'm new to python. I have the following list of books stored on the linked list and I want to sort them by using quicksort but unfortunately, I'm stuck on a problem.
class Node:
def __init__(self, data=None):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append_value(self, x):
if not isinstance(x, Node):
x = Node(x)
if self.is_empty():
self.head = x
else:
current = self.head
while current.next:
current = current.next
current.next = x
x.prev = current
self.tail = x
def length(self):
count = 0
current = self.head
while current:
count += 1
current = current.next
return count
def is_empty(self):
return self.head is None
def __str__(self):
to_print = ''
current = self.head
while current:
to_print += f'{current.data} <-> '
current = current.next
if to_print:
return f'[{to_print[:-5]}]'
return '[]'
def quick_sort(self, arr):
if self.length() < 2:
return self
else:
pivot = self.tail.data
smaller, equal, larger = [], [], []
current = self.head
while current:
if current.data < pivot:
smaller.append(current.data)
elif current.data == pivot:
equal.append(current.data)
else:
larger.append(current.data)
current = current.next
return self.quick_sort(smaller) + equal + self.quick_sort(larger)
This is the quicksort method but it's giving me RecursionError on 'return self.quick_sort(smaller) + equal + self.quick_sort(larger)'. How do I sort the linked list by using quicksort?
my_list = DoublyLinkedList()
my_list.append_value('In Search of Lost Time')
my_list.append_value('Ulysses by James Joyce')
my_list.append_value('Within a Budding Grove')
my_list.append_value('The Guermantes Way')
my_list.append_value('In Search of Lost Time')
my_list.append_value('Sodom & Gomorrah')
my_list.append_value('One Hundred Years of Solitude')
my_list.append_value('War and Peace')
print(f'List of Books: {my_list}')
print(f'Quick Sort: {my_list.quick_sort(my_list)}')
Indeed, the error occurs because you pass a standard list to quick_sort, while it expects the argument to be a doubly linked list instance.
Moreover, it would be strange if the use of lists were allowed in this algorithm, as then one may wonder why there is a doubly linked list in the first place. If you're going to use lists, then you might as well store the data in a list and sort the list. This cannot be the purpose.
Some other comments about the code:
quick_sort is a method of the class, so it should not be necessary to pass the linked list also as argument. Instead, pass two arguments that identify the start and end node of a subsection in that linked list.
The final return statement is problematic. If indeed quick_sort is going to return a linked list, then + is not an operator you can use on those. Moreover, Quick Sort is supposed to be an in-place sorting algorithm, while + suggests a new list being created. As it is in-place, you should be able to just return self.
So, ... you really need to solve this by walking through the linked list and manipulate it.
Here is one way to do it. First define two methods that allow inserting and deleting a node anywhere in the list:
def remove_node(self, node):
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
node.next = node.prev = None
return node
def insert_after(self, prev, node):
if not isinstance(node, Node):
node = Node(node)
node.prev = prev
if prev:
node.next = prev.next
prev.next = node
else:
node.next = self.head
self.head = node
if node.next:
node.next.prev = node
else:
self.tail = node
return self
The latter is in fact a more flexible method than the append_value you already had. You could actually make use of this new one to define yours:
def append_value(self, x):
return self.insert_after(self.tail, x)
Then perform the quick sort as follows:
Take a start and end node as arguments. Extract (remove) the end node from the list and consider it the pivot. Let two references walk along this sublist towards each other, starting at the ends. When their values are at the good side of the pivot value, let that reference move closer. Once you have two references where the value is opposite from the pivot, swap the data that is in these two nodes. Once these two references cross each other you have identified the two partitions. Inject the pivot node back into the list, right between those two partitions. Finally, use recursion to do the same with the two partitions:
def quick_sort(self, start=None, end=None):
if not start and not end: # set default arguments:
start = self.head
end = self.tail
if not start or not end or start == end or end.next == start:
# The sublist is empty or has just one value
return self
# Extract the pivot node from the list
end, pivot = end.prev, self.remove_node(end)
pivotdata = pivot.data
# Define two references that will walk towards eachother:
right = end
left = start
while left and left.prev != right: # While they didn't cross over
if left.data <= pivotdata:
left = left.next
elif right.data >= pivotdata:
right = right.prev
else: # Swap values, not the nodes:
left.data, right.data = right.data, left.data
left = left.next
right = right.prev
# Insert the pivot node between the two partitions
self.insert_after(right, pivot)
# Sort the non-empty partitions recursively
if start.prev != pivot:
self.quick_sort(start, right)
if end.next != pivot:
self.quick_sort(left, end)
return self