A linked list is a data structure that consists of a collection of nodes, where each node contains an element and a reference to the next node in the list. In this article, we will discuss how to sort a linked list in C using different sorting algorithms, along with code examples.
- Bubble sort
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
void bubbleSort(struct Node *start)
{
int swapped, i;
struct Node *ptr1;
struct Node *lptr = NULL;
/* Checking for empty list */
if (start == NULL)
return;
do
{
swapped = 0;
ptr1 = start;
while (ptr1->next != lptr)
{
if (ptr1->data > ptr1->next->data)
{
swap(ptr1, ptr1->next);
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
}
while (swapped);
}
- Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. It compares the current element with the elements in the sorted sub-list, and inserts the current element at its correct position.
void insertionSort(struct Node *start)
{
struct Node *ptr, *temp;
ptr = start->next;
while (ptr != NULL)
{
temp = ptr->next;
sortedInsert(ptr);
ptr = temp;
}
}
- Selection Sort
Selection sort is an in-place comparison-based sorting algorithm. It divides the input list into two parts: the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire input list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.
void selectionSort(struct Node *start)
{
struct Node *ptr, *temp;
ptr = start;
while (ptr->next != NULL)
{
temp = ptr;
while (temp->next != NULL)
{
if (temp->next->data < ptr->data)
ptr = temp->next;
temp = temp->next;
}
swap(ptr, start);
start = start->next;
}
}
- Merge Sort
Merge sort is a divide and conquer algorithm that divides the list into two sub-lists, recursively sorts the sub-lists, and then merges the sorted sub-lists to produce the final sorted list.
struct Node* mergeSort(struct Node* head)
{
if ((head == NULL) || (head->next == NULL))
{
return head;
}
struct Node* middle = getMiddle(head);
struct Node* nextofmiddle = middle->next;
middle->
Sure, here are some additional topics related to sorting linked lists in C:
5. Quick Sort
Quick sort is a divide and conquer algorithm that selects a 'pivot' element from the list and partitions the other elements into two sub-lists, according to whether they are less than or greater than the pivot. The sub-lists are then recursively sorted.
struct Node *partition(struct Node *l, struct Node *h)
{
// set pivot as h element
int x = h->data;
// similar to i = l-1 for array implementation
struct Node *i = l->prev;
for (struct Node *j = l; j != h; j = j->next)
{
if (j->data <= x)
{
// Similar to i++ for array
i = (i == NULL)? l : i->next;
swap(&(i->data), &(j->data));
}
}
i = (i == NULL)? l : i->next; // Similar to i++
swap(&(i->data), &(h->data));
return i;
}
6. Radix Sort
Radix sort is an integer sorting algorithm that sorts data with integer keys by grouping the keys by individual digits that share the same significant position and value.
void radixsort(struct Node *start, int maxx)
{
int i;
for (i = 1; maxx/i > 0; i *= 10)
countSort(start, i);
}
7. Hybrid Sort
Hybrid sort is a sorting algorithm that combines two or more sorting algorithms to achieve better performance. For example, you could use quick sort to sort a large portion of the list, and then use insertion sort to sort the remaining small portion of the list.
8. Other Considerations
When implementing a sorting algorithm for a linked list, it is important to keep in mind that unlike an array, a linked list does not have a built-in mechanism for accessing elements by index. This means that you will need to use pointers to traverse the list and swap elements. Additionally, the time complexity of sorting a linked list can be affected by the method used to insert and delete elements from the list. A sorted linked list can also be used to implement a data structure such as a priority queue.
Please keep in mind that these are just examples and not production ready code. It is important to thoroughly test and debug your code before using it in any production environment.
## Popular questions
1. What is a linked list and why is it used in sorting algorithms?
A linked list is a data structure that consists of a collection of nodes, where each node contains an element and a reference to the next node in the list. Linked lists are used in sorting algorithms because they allow for efficient insertion and deletion of elements, which is useful when implementing certain sorting algorithms like insertion sort and merge sort.
2. What is the difference between an in-place sorting algorithm and a comparison-based sorting algorithm?
An in-place sorting algorithm is a sorting algorithm that sorts the input list without using any additional memory. A comparison-based sorting algorithm is a sorting algorithm that sorts the input list by comparing elements.
3. What is the time complexity of the bubble sort algorithm when applied to a linked list?
The time complexity of the bubble sort algorithm when applied to a linked list is O(n^2), where n is the number of elements in the list.
4. Can you explain the process of sorting a linked list using the merge sort algorithm?
The merge sort algorithm is a divide and conquer algorithm that divides the list into two sub-lists, recursively sorts the sub-lists, and then merges the sorted sub-lists to produce the final sorted list. The process begins by dividing the input list into two equal sub-lists, and then recursively sorting each sub-list. The two sorted sub-lists are then merged together to form a single sorted list.
5. How can the time complexity of sorting a linked list be affected by the method used to insert and delete elements from the list?
The time complexity of sorting a linked list can be affected by the method used to insert and delete elements from the list. For example, if elements are inserted and deleted using a technique that maintains the sorted order of the list, then the time complexity of sorting the list will be reduced. On the other hand, if elements are inserted and deleted in a way that disrupts the sorted order of the list, then the time complexity of sorting the list will be increased.
### Tag
Sorting
