Insertion sort for doubly-linked lists

4. Insertion sort for doubly-linked lists [4]. From the prerequisite course, you have learned that Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. Insertion sort for a doubly-linked list operates similarly to the insertion sort algorithm used for arrays. Starting with the second list element, each element in the linked list is visited. Each visited element is moved back as needed and inserted into the correct position in the list’s sorted portion. The python code of Insertion sort for doubly-linked lists is shown below.

The Correct Answer and Explanation is :

nsertion sort is a straightforward algorithm that constructs a sorted sequence incrementally, processing one element at a time.hen applied to a doubly linked list, the algorithm operates similarly to its array-based counterpart but leverages the bidirectional pointers for efficient insertion operations.
Python Implementation:

“python
class Node:
def init(self, data):
self.data = data
self.prev = None
self.next = None

def insertion_sort(head):
if not head:
return head

current = head.next
while current:
    key = current
    move = current.prev
    while move and key.data < move.data:
        move = move.prev

    next_current = current.next

    # Detach key node
    if current.prev:
        current.prev.next = current.next
    if current.next:
        current.next.prev = current.prev

    # Insert key node at correct position
    if not move:
        # Insert at the beginning
        key.next = head
        key.prev = None
        head.prev = key
        head = key
    else:
        key.next = move.next
        key.prev = move
        if move.next:
            move.next.prev = key
        move.next = key

    current = next_current

return head

“`
Explanation:

1. Node Class Definition: Node class is defined to represent each element in the doubly linked list, containing data, prev (pointer to the previous node), and next (pointer to the next node).
2. Function insertion_sort: his function takes the head of the doubly linked list as its parameter. If the list is empty (head is None), it returns None.
3. Traversal: he algorithm starts with the second node (head.next) and iterates through each node (current). For each current node, it identifies the correct position in the sorted portion of the list by comparing current.data with the data in the preceding nodes (move).
4. Finding the Insertion Point: he inner while loop moves backward through the sorted portion of the list to find the appropriate spot where the current node should be inserted.
5. Detaching the Current Node: efore insertion, the current node is detached from its original position by updating the next pointer of its prev node and the prev pointer of its next node.
6. Inserting the Node:

• At the Beginning: f no node in the sorted portion has a value less than current.data (move becomes None), the current node is inserted at the beginning. – Elsewhere: therwise, the current node is inserted after the move node.

1. Updating Pointers: fter insertion, the prev and next pointers of the involved nodes are updated to maintain the integrity of the doubly linked list structure.
2. Advancing to the Next Node: he current pointer is moved to the next node in the original list (next_current), and the process repeats until all nodes are processed.
   Time Complexity:

he time complexity of this insertion sort implementation on a doubly linked list is (O(n^2)) in the worst case, where (n) is the number of nodes. This is because, for each node, the algorithm may traverse a significant portion of the sorted list to find the correct insertion point.
Advantages:

• Stability: nsertion sort maintains the relative order of equal elements, making it a stable sorting algorithm.
• Simplicity: he algorithm is straightforward to implement and understand.
• Efficiency for Small or Nearly Sorted Lists: nsertion sort performs efficiently for small datasets or lists that are already partially sorted.
  Conclusion:

mplementing insertion sort on a doubly linked list involves iterating through the list, detaching each node, and inserting it into its correct position within the sorted portion. The bidirectional nature of doubly linked lists facilitates efficient insertion operations, as nodes can be easily re-linked in both forward and backward directions.