I want to make bubble sorting algorithm with doubly linked list in python.
Node has prev key and next key. The list connected end node and start node(head)
This is My Node defenition
class Node:
def __init__(self, key):
self.key = key
self.prev = None
self.next = None
and this is my list def
class MyList:
def __init__(self):
self.head = None
~~~
def insert(self, x, y=None):
if y is None:
# add to tail
if self.head is None:
self.head = MyNode(x.key)
self.head.prev = self.head
self.head.next = self.head
return True
x.prev = self.head.prev
x.next = self.head
self.head.prev.next = x
self.head.prev = x
else:
# insert x after y
x.prev = y
x.next = y.next
y.next.prev = x
y.next = x
def delete(self, x):
if self.head is self.head.prev and self.head.next:
self.head.prev = None
self.head.next = None
self.head = None
return
node_x = self.search(x.key)
if node_x is None:
return
if node_x is self.head:
self.head = self.head.next
node_x.prev.next = node_x.next
node_x.next.prev = node_x.prev
def search(self, k):
curr = self.head.next
while curr.key is not self.head.key:
if curr.key == k:
return curr
curr = curr.next
return curr
and this is swap function and sort function <- this doesnt work
def swap(l, x, y):
if x == y:
return
node_x = l.search(x)
node_y = l.search(y)
if node_x is None or node_y is None:
return
prev_x = node_x.prev
prev_y = node_y.prev
l.delete(node_x)
l.delete(node_y)
if prev_x is not None:
l.insert(node_y, prev_x)
else:
l.insert(node_y)
if prev_y is not None:
l.insert(node_x, prev_y)
else:
l.insert(node_x)
def bubble_sort(l):
n = len(l)
curr = l.head
for i in range(n + 1):
if curr.key > curr.next.key:
swap(l, curr.key, curr.next.key)
curr = curr.next
swap function doesn't work properly. This is Error code
MyList.tolist(self)
11 if x.next is self.head:
12 break
---> 13 assert x.next.prev is x
14 x = x.next
16 return r
AssertionError:
I tried to fix swap function but it cannot work. How to fix it?
There are several issues:
swap function is overly complex. It gets values as argument, while the caller knows what the nodes are, but leaves it for swap to search for them again.None links, but that never happens in a circular list.head of the list, while this will be needed when one of the two given nodes is the head.node_y is the successor of node_x (which is your case), then prev_y will be node_x, and so with l.insert(node_x, prev_y) you actually call l.insert(node_x, node_x), creating havoc in the list.curr = curr.next after the swap, but by the swap (if it would work as expected), you have already moved with curr one step ahead in the list, so now you skip a node.Make the process easier (and faster) and don't rewire the nodes that need swapping, but leave them where they are: instead swap their keys.
Here is the corrected bubble sort function:
def bubble_sort(l):
if not l.head: # Nothing to do
return
dirty = True
while dirty: # need an extra loop
dirty = False
curr = l.head # need to start here
while curr.next is not l.head: # no need of len(l)
if curr.key > curr.next.key:
# swap the keys instead of the nodes
curr.key, curr.next.key = curr.next.key, curr.key
dirty = True
curr = curr.next
If you really want to rewire the nodes, then make use of the fact that the swap is always about two consecutive nodes, so that it actually comes down to moving one node:
def bubble_sort(l):
dirty = True
while dirty: # need an extra loop
dirty = False
curr = l.head # need to start here
while curr.next is not l.head: # no need of len(l)
if curr.key > curr.next.key:
node = curr.next
l.delete(curr)
l.insert(curr, node)
dirty = True
else:
curr = curr.next