Sorting a Linked list in Data structures

Sorting – linked list: there are many algorithms to sort a linked list like the bubble sort, merge sort, etc. so today we are going to sort a linked list by exchanging the values of nodes using the bubble sort algorithm.

Sorting a linked list using the bubble sort algorithm

In a bubble to sort a linked list that has n items, we need to iterate over the list n-1 times. like in the example we have a list of 5 items then we need to iterate over the list for 4 times.

to sort a linked list first we need three references p, q, and end. in the first iteration, we set the end variable to None. and in every iteration, we set the p variable to the first node of the list and the q variable to the second node of the list.

if in the iteration the value of the linked part of node p is equal to the end then we break the iteration and continue to the next iteration.

if the info part of node p is greater than the info part of node q then we swap the values of node p and q otherwise we refer p and q to the next node of the list. so in the given example list, the value of node p is not greater than the value of the q node so we refer p and q to the next node of the list.

here also the value of node p is not greater than the value of node q so we go to the next nodes.

here the value of node p is greater than the value of node q so we swap them.

next, we go to the next nodes here the value of node p is not greater than the value of node q so we don’t swap them.

now we go to the next nodes of the list. here the value of the linked part of node p is equal to the end variable. so here the first iteration ends.

now after iteration one ends, the last node of the list becomes sorted so we refer the end variable to the last node of the list.

now the second iteration starts and in the second iteration, we refer the variables p and q to the first and second node of the list and swap values of nodes p and q if the values of node p are greater than the value of node q.

this condition will run till the linked part of node p does not become equal to the end variable. as you see in the images given below.

and after every iteration, we update the value of the variable end. because if we iterate the list over two times then the last two nodes of the list become sorted. so we don’t need to check them again.

so after performing the n-1 iterations over the linked list. where n is the size of the list. now our list becomes sorted.

def bubble_sort_exdata(self):
    end = None
    while end != self.start.link:
        p = self.start
        while p.link != end:
            q = p.link
            if p.info > q.info:
                p.info, q.info = q.info, p.info
            p = p.link
        end = p