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()