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:
    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()
Comparing First node with second node
Comparing a node with its next node

Output

Python Bubble Sort Output

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *