Iterative selection sort for linked list | Linked List Node ; Function to sort a linked list using selection sort algorithm by swapping the next pointers ; While b is not the last node ; While d is pointing to a valid node ; If d appears immediately after b ; Case 1 : b is the head of the linked list ; Move d before b ; Swap b and d pointers ; Update the head ; Skip to the next element as it is already in order ; Case 2 : b is not the head of the linked list ; Move d before b ; Swap b and d pointers ; Skip to the next element as it is already in order ; If b and d have some non - zero number of nodes in between them ; Case 3 : b is the head of the linked list ; Swap b . next and d . next ; Swap b and d pointers ; Skip to the next element as it is already in order ; Update the head ; Case 4 : b is not the head of the linked list ; Swap b . next and d . next ; Swap b and d pointers ; Skip to the next element as it is already in order ; Update c and skip to the next element as it is already in order ; Function to print the list ; Driver Code
class Node : NEW_LINE INDENT def __init__ ( self , val ) : NEW_LINE INDENT self . data = val NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def selectionSort ( head ) : NEW_LINE INDENT a = b = head NEW_LINE while b . next : NEW_LINE INDENT c = d = b . next NEW_LINE while d : NEW_LINE INDENT if b . data > d . data : NEW_LINE INDENT if b . next == d : NEW_LINE INDENT if b == head : NEW_LINE INDENT b . next = d . next NEW_LINE d . next = b NEW_LINE b , d = d , b NEW_LINE c = d NEW_LINE head = b NEW_LINE d = d . next NEW_LINE DEDENT else : NEW_LINE INDENT b . next = d . next NEW_LINE d . next = b NEW_LINE a . next = d NEW_LINE b , d = d , b NEW_LINE c = d NEW_LINE d = d . next NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if b == head : NEW_LINE INDENT r = b . next NEW_LINE b . next = d . next NEW_LINE d . next = r NEW_LINE c . next = b NEW_LINE b , d = d , b NEW_LINE c = d NEW_LINE d = d . next NEW_LINE head = b NEW_LINE DEDENT else : NEW_LINE INDENT r = b . next NEW_LINE b . next = d . next NEW_LINE d . next = r NEW_LINE c . next = b NEW_LINE a . next = d NEW_LINE b , d = d , b NEW_LINE c = d NEW_LINE d = d . next NEW_LINE DEDENT DEDENT DEDENT else : NEW_LINE INDENT c = d NEW_LINE d = d . next NEW_LINE DEDENT DEDENT a = b NEW_LINE b = b . next NEW_LINE DEDENT return head NEW_LINE DEDENT def printList ( head ) : NEW_LINE INDENT while head : NEW_LINE INDENT print ( head . data , end = " ▁ " ) NEW_LINE head = head . next NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT head = Node ( 5 ) NEW_LINE head . next = Node ( 4 ) NEW_LINE head . next . next = Node ( 3 ) NEW_LINE head = selectionSort ( head ) NEW_LINE printList ( head ) NEW_LINE DEDENT