Sorting is a crucial process in the field of computer science, reaching its peak in QuickSort. QuickSort stands out as a divide-and-conquer technique known for its effectiveness. Adapting QuickSort for linked lists is a valuable ability, even though it is typically used for arrays. This guide explores the process of implementing QuickSort on singly linked lists using C++, offering an in-depth tutorial complete with code snippets, illustrations, and results.
What is a QuickSort?
QuickSort operates by splitting the dataset and sorting smaller portions iteratively. It selects a 'pivot' element to divide the dataset into sub-arrays according to their comparison with the pivot. The strength of QuickSort stems from its capability to sort elements in situ and parallel sorting during partitioning.
Implementing QuickSort on Singly Linked Lists
To customize QuickSort for singly linked lists, essential functions must be specified: one for dividing the list, another for choosing a pivot, and the main QuickSort function for sorting recursively. Now, let's delve into the C++ implementation:
Code:
#include <iostream>
// Node structure for the singly linked list
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
// Function to find the last node of the linked list
Node* getTail(Node* head) {
while (head != nullptr && head->next != nullptr) {
head = head->next;
}
return head;
}
// Function to partition the linked list and return the pivot node
Node* partition(Node* head, Node* end, Node** newHead, Node** newEnd) {
Node* pivot = end;
Node* prev = nullptr, *cur = head, *tail = pivot;
while (cur != pivot) {
if (cur->data < pivot->data) {
if (*newHead == nullptr)
*newHead = cur;
prev = cur;
cur = cur->next;
} else {
if (prev)
prev->next = cur->next;
Node* temp = cur->next;
cur->next = nullptr;
tail->next = cur;
tail = cur;
cur = temp;
}
}
if (*newHead == nullptr)
*newHead = pivot;
*newEnd = tail;
return pivot;
}
// Recursive function to perform QuickSort on the linked list
Node* quickSortRecur(Node* head, Node* end) {
if (!head || head == end)
return head;
Node* newHead = nullptr, *newEnd = nullptr;
Node* pivot = partition(head, end, &newHead, &newEnd);
if (newHead != pivot) {
Node* temp = newHead;
while (temp->next != pivot)
temp = temp->next;
temp->next = nullptr;
newHead = quickSortRecur(newHead, temp);
temp = getTail(newHead);
temp->next = pivot;
}
pivot->next = quickSortRecur(pivot->next, newEnd);
return newHead;
}
// Wrapper function for QuickSort on a linked list
void quickSort(Node** headRef) {
*headRef = quickSortRecur(*headRef, getTail(*headRef));
}
// Function to print the linked list
void printList(Node* node) {
while (node != nullptr) {
std::cout << node->data << " ";
node = node->next;
}
std::cout << std::endl;
}
// Function to add a new node to the linked list
void push(Node** headRef, int newData) {
Node* newNode = new Node(newData);
newNode->next = *headRef;
*headRef = newNode;
}
// Driver code
int main() {
Node* head = nullptr;
// Adding elements to the linked list
push(&head, 12);
push(&head, 9);
push(&head, 15);
push(&head, 5);
push(&head, 6);
std::cout << "Linked List before sorting: ";
printList(head);
quickSort(&head);
std::cout << "Linked List after sorting: ";
printList(head);
return 0;
}
Output:
Linked List before sorting: 12 9 15 5 6
Linked List after sorting: 5 6 9 12 15
Conclusion:
In summary, integrating QuickSort into linked lists in C++ enhances understanding of sorting algorithms. The code demonstrates intricate pointer manipulation and recursive functions, showcasing QuickSort's versatility across different data structures. QuickSort proves to be a powerful method for sorting large datasets efficiently, boasting an average time complexity of O(n log n).
The illustrated situation and resulting outcome clearly showcase the algorithm's ability to smoothly convert a disordered linked list into an ordered one. Competence in these adjustments indicates a strong grasp of algorithmic concepts, providing developers with flexible mechanisms for efficient data handling.
In the field of computer science, QuickSort continues to be highly regarded, especially when applied to linked lists, demonstrating the adaptability necessary for solving various computational problems. By studying and applying these algorithms, programmers can improve their algorithmic expertise and highlight the efficiency and complexity of efficient sorting techniques. Examining QuickSort in the context of linked lists refines algorithmic abilities and emphasizes the elegance and effectiveness of advanced sorting approaches.
