Bubble sort: In this sorting algorithm, adjacent nodes are compared and swapped if they are in wrong order.

Singly linked list:

Algorithm:

• Create a boolean variable swapped
• Create a loop until no more swaps are made
• Set swapped to false
• Point curr to head and prev to NULL
• Iterate over the list with curr and prev
• Compare the value of current node with next node
• If the value of current is greater than that of next, swap
• Set swapped as true
• After completing one pass, check if any swaps were made
• If no swaps were made, exit the loop

Code:

node* bubbleSort(node* head) {

if (head == NULL || head->next == NULL) {

return head;

}

bool swapped = true;

node* curr = head;

node* prev = NULL;

while (swapped) {

swapped = false;

curr = head;

prev = NULL;

while (curr->next != NULL) {

if (curr->val > curr->next->val) {

if (prev != NULL) {

prev->next = curr->next;

}

else {

head = curr->next;

}

node* temp = curr->next->next;

curr->next->next = curr;

curr->next = temp;

swapped = true;

}

prev = curr;

curr = curr->next;

}

}

return head;

}

Doubly linked list:

Algorithm:

• Set a boolean variable ‘swapped’ to ‘true’.
• Enter a loop that continues until no more swaps are made:
• Set ‘swapped’ to ‘false’.
• Set the current node (‘curr’) to the head of the doubly linked list.
• Iterate over the doubly linked list by moving the ‘curr’ pointer:

- Compare the value of the current node with the value of the next node.

- If the value of the current node is greater than the value of the next node, perform a swap:

- Adjust the next and previous pointers of the adjacent nodes to maintain the doubly linked list structure.

- Update the ‘next’ and ‘prev’ pointers of the swapped nodes.

- Set ‘swapped’ to ‘true’ to indicate that a swap has occurred.

- Move the ‘curr’ pointer to the next node in the doubly linked list.

• After completing one pass of the doubly linked list, check if any swaps were made (‘swapped == true’).
• If no swaps were made, exit the loop.

Code:

node* bubbleSort(node* head) {

if (head == NULL || head->next == NULL) {

return head;

}

bool swapped = true;

node* curr = head;

while (swapped) {

swapped = false;

curr = head;

while (curr->next != NULL) {

if (curr->val > curr->next->val) {

// Swap nodes

node* prev = curr->prev;

node* n = curr->next;

node* p = n->next;

// Update prev and next pointers of adjacent nodes

if (prev != NULL) {

prev->next = n;

}

else {

head = n;

}

n->prev = prev;

n->next = curr;

curr->prev = n;

curr->next = p;

if (p != NULL) {

p->prev = curr;

}

swapped = true;

}

curr = curr->next;

}

}

return head;

}

Insertion sort:

Algorithm:

• Create a new sorted linked list, initially empty.
• Traverse the original linked list from the head.
• For each node in the original linked list:
• Remove the current node from the original list.
• Find the proper position to insert the current node in the sorted list by comparing its value with the values of nodes in the sorted list.
• Insert the current node at the correct position in the sorted list.
• Return the head of the sorted linked list.

Code:

node* insertionSort(node* head) {

if (head == NULL || head->next == NULL) {

return head;

}

node* sorted = NULL;

node* curr = head;

while (curr != NULL) {

node* next = curr->next;

node* sortedCurr = sorted;

node* prev = NULL;

while (sortedCurr != NULL && sortedCurr->val < curr->val) {

prev = sortedCurr;

sortedCurr = sortedCurr->next;

}

if (prev != NULL) {

prev->next = curr;

}

else {

sorted = curr;

}

curr->next = sortedCurr;

curr = next;

}

return sorted;

}

Selection sort: Selection sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion of the list and moves it to the sorted portion.

Algorithm:

• Start with the head of the linked list as the current minimum.
• Iterate over the linked list, considering the current node as the minimum:
• Find the node with the minimum value in the remaining unsorted portion of the list.
• Swap the values of the current minimum node and the found minimum node.
• Move the boundary of the sorted portion by advancing the current minimum to the next node.
• Repeat steps 2 and 3 until the entire list is sorted.

Code:

node* findMinimum(node* head) {

node* minNode = head;

node* curr = head->next;

while (curr != NULL) {

if (curr->val < minNode->val) {

minNode = curr;

}

curr = curr->next;

}

return minNode;

}

node* selectionSort(node* head) {

node* sortedHead = NULL;

node* sortedTail = NULL;

while (head != NULL) {

node* minNode = findMinimum(head);

if (minNode == head) {

// Move head forward

head = head->next;

}

else {

// Remove minNode from current position

node* prev = head;

while (prev->next != minNode) {

prev = prev->next;

}

prev->next = minNode->next;

// Insert minNode at the sorted list's tail

minNode->next = NULL;

if (sortedHead == NULL) {

sortedHead = sortedTail = minNode;

}

else {

sortedTail->next = minNode;

sortedTail = minNode;

}

}

}

return sortedHead;

}

Merge Sort:

Algorithm:

• If the linked list has 0 or 1 node, it is already sorted, so return the head of the list.
• Split the linked list into two halves using the fast-slow pointer technique.
• Recursively apply Merge Sort to the two halves.
• Merge the two sorted halves by repeatedly selecting the smaller node from each half and adjusting the pointers accordingly.

Code:

node* getMiddle(node* head) {

if (head == NULL || head->next == NULL) {

return head;

}

node* slow = head;

node* fast = head->next;

while (fast != NULL && fast->next != NULL) {

slow = slow->next;

fast = fast->next->next;

}

node* middle = slow->next;

slow->next = NULL;

return middle;

}

node* merge(Node* list1, node* list2) {

node* dummyHead = new node(0);

node* tail = dummyHead;

while (list1 != NULL && list2 != NULL) {

if (list1->val < list2->val) {

tail->next = list1;

list1 = list1->next;

}

else {

tail->next = list2;

list2 = list2->next;

}

tail = tail->next;

}

if (list1 != NULL) {

tail->next = list1;

}

if (list2 != NULL) {

tail->next = list2;

}

node* sortedHead = dummyHead->next;

delete dummyHead;

return sortedHead;

}

node* mergeSort(node* head) {

if (head == NULL || head->next == NULL) {

return head;

}

node* middle = getMiddle(head);

node* left = mergeSort(head);

node* right = mergeSort(middle);

return merge(left, right);

}

Quick Sort: Quick sort is a popular sorting algorithm that follows the divide-and-conquer approach. It works by selecting a pivot element from the list and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

Algorithm:

• If the list is empty or has only one node, it is already sorted, so return the head of the list.
• Select a pivot element from the list. In this case, we can choose the head node as the pivot.
• Partition the list into two sub-lists:
  • Create two empty lists, lessHead and greaterHead, to hold the elements less than and greater than the pivot, respectively.
  • Traverse the list from the second node onwards:
  • If the current node's value is less than the pivot, append it to lessHead.
  • Otherwise, append it to greaterHead.
• Recursively sort the lessHead and greaterHead lists using quick sort.
• Combine the sorted lessHead, pivot, and sorted greaterHead lists:
  • If lessHead is not empty, set its last node's next pointer to the pivot.
  • If greaterHead is not empty, set the pivot's next pointer to the head of greaterHead.
• Return the head of the sorted list.

Code:

node* getTail(Node* head) {

if (head == NULL) {

return NULL;

}

while (head->next != NULL) {

head = head->next;

}

return head;

}

node* partition(Node* head, Node* end, Node** newHead, Node** newEnd) {

node* pivot = end;

node* prev = NULL;

node* curr = head;

node* tail = pivot;

while (curr != pivot) {

if (curr->val < pivot->val) {

if (*newHead == NULL) {

*newHead = curr;

}

prev = curr;

curr = curr->next;

}

else {

if (prev != NULL) {

prev->next = curr->next;

}

node* temp = curr->next;

curr->next = NULL;

tail->next = curr;

tail = curr;

curr = temp;

}

}

if (*newHead == NULL) {

*newHead = pivot;

}

*newEnd = tail;

return pivot;

}

node* quickSort(node* head, node* end) {

if (head == NULL || head == end) {

return head;

}

node* newHead = NULL;

node* newEnd = NULL;

node* pivot = partition(head, end, &newHead, &newEnd);

if (newHead != pivot) {

node* temp = newHead;

while (temp->next != pivot) {

temp = temp->next;

}

temp->next = NULL;

newHead = quickSort(newHead, temp);

temp = getTail(newHead);

temp->next = pivot;

}

pivot->next = quickSort(pivot->next, newEnd);

return newHead;

}