I have been doing DSA lately on python, this time tried bubble-sort algorithm on a doubly linked list.
Unfortunately, the method is not giving proper result.
Please correct me, tell me where I am going wrong (I tried a lot but couldn't understand). Please explain and suggest the required changes.
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.next = None
self.prev = None
self.count = 0
def bubble_sort(self):
if self.head is None:
return f"Linked list is empty!"
elif self.head.next is None:
return self.head
else:
left = self.head
right = self.head.next
while True:
flag = 'sorted'
while True:
if right is None:
break
if left.value > right.value:
flag = 'unsorted'
if (left == self.head) and (right == self.tail): #only two nodes
self.tail = left
self.head = right
elif left == self.head: #edge case of left
self.head = right
elif right == self.tail: #edge case of right
self.tail = left
temp_right = right.next
temp_left = left.prev
left.next = temp_right
left.prev = right
right.next = left
right.prev = temp_left
right = left.next
else:
left = left.next
right = right.next
left = self.head
right = self.head.next
if flag == 'sorted':
return self
Please help!
When you swap two nodes somewhere in the middle of a doubly linked list, there are 4 nodes involved, and your code has correctly identified them.
Between those 4 nodes there are 6 links: between the first pair there are 2 links, between the middle pair there are 2 links, and between the right pair there are 2 links.
Your code only updates four links, so this cannot be correct. Namely, you have not updated the temp_left.next and temp_right.prev links.
To fix this, change the swapping code as follows:
temp_right = right.next
temp_left = left.prev
left.next = temp_right
left.prev = right
right.next = left
right.prev = temp_left
## === start of fix === insert these statements:
if temp_right:
temp_right.prev = left
if temp_left:
temp_left.next = right
## === end of fix ===
right = left.next
Not your question, but it should be noted that bubble sort isn't really a good choice for sorting, and even less for sorting linked lists: the overhead for performing a swap is really too heavy. Merge sort would be a better choice.