Elements of a linear linked list can be sorted in many ways. In this post We will use Python Bubble Sort to sort a Linear linked list.
Working of Python Bubble Sort
Bubble sort works in passes, comparisons and interchanges. A pass is a complete round in which elements are compared and the biggest element still to be sorted, Bubbles out to its correct position.
In a pass one element is compared with its next element. If the element is bigger than the next one, they are interchanged. If the element is smaller than its next element then no interchange takes place. The next element is then compared with its next element. This process is continued till the second last element is compared with the last element.
The total numbers of passes are one less than the total number of elements to be sorted. If N is the number of elements then number of passes is N-1. 8 elements will be sorted in 7 passes, 18 elements will be sorted in 17 passes and 100 elements will be sorted in 99 passes.
The number of comparisons in each pass is equal to Number of elements – the pass number. If N is the number of elements and Kth pass is being processed, then the number of comparisons is N-K. If you begin the number of passes with zero then the number of comparisons in Kth Pass will be N-K-1.
Python Bubble Sort Program for Linear Linked List
In this program the linear liked list is created using the user defined class Node. A node represents an element of the linked list with data and link part.
User defined class LinearList has two data members, start and nodecount. Start pointer stores address of first element of the linked list. Nodecount stores the number of nodes in the Linear Linked List.
The nodes of the linked list are added at the beginning. Every time a new node is added nodecount is incremented to update the number of nodes.
#user defined class for nodes
class Node:
def __init__(self, data=None, link=None):
self.data=data
self.link=link
def __str__(self):
return str(self.data)
#user defined class for Linked list
class LinearList:
def __init__(self, start=None,nodecount=0):
self.start=start
self.nodecount=nodecount #stores number of nodes in linked list
def addBegNode(self, value=None):#Adding nodes at beginning
node=Node(value)
node.link=self.start
self.start=node
self.nodecount=self.nodecount+1
def printList(self):#traverse abd display nodes
ptr=self.start
while ptr:
print(ptr)
ptr=ptr.link
print()
def bubbsort(self):
for i in range(self.nodecount-1):#for controlling passes of Bubble Sort
curr=self.start
nxt=curr.link
prev=None
while nxt:#Comparisons in passes
if curr.data>nxt.data:
if prev==None:
prev=curr.link
nxt=nxt.link
prev.link=curr
curr.link=nxt
self.start=prev
else:
temp=nxt
nxt=nxt.link
prev.link=curr.link
prev=temp
temp.link=curr
curr.link=nxt
else:
prev=curr
curr=nxt
nxt=nxt.link
i=i+1
#Create blank Linked List
ll=LinearList()
numele= input('How many elements to be added in the Linked List??')
#add nodes at begging in the Linked List
for cnt in range(int(numele)):
ele= input('Enter a value to be added at the beginning of the Linked List ')
ll.addBegNode(ele)
cnt=cnt+1
#Print Linked List before sorting
print("Linked List Initially")
ll.printList()
ll.bubbsort()
#Print Linked List After sorting
print("Linked List after sorting")
ll.printList()
Output
Be First to Comment