# Python Bubble Sort to sort a Linear Linked List

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:
self.data=data
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
node=Node(value)
self.start=node
self.nodecount=self.nodecount+1

def printList(self):#traverse abd display nodes
ptr=self.start
while ptr:
print(ptr)
print()

def bubbsort(self):
for i in range(self.nodecount-1):#for controlling passes of Bubble Sort
curr=self.start
prev=None
while nxt:#Comparisons in passes
if curr.data>nxt.data:
if prev==None:
self.start=prev
else:
temp=nxt
prev=temp
else:
prev=curr
curr=nxt
i=i+1

ll=LinearList()
for cnt in range(int(numele)):
ele= input('Enter a value to be added at the beginning of the Linked List ')