The most efficient sorting algorithm in general, quicksort, is applicable to arrays because elements in
arrays can be accessed in O(1) time based on indexes. It takes more time to locate a node in a list, so we
have to utilize other algorithms to sort lists.
Let’s take a list with four nodes as an example to analyze the process of the insert sort algorithm
(Figure 3-6(a)). A list is split into two parts. The first part contains nodes already sorted, and the second
part is not sorted yet. The node pointed by P1 is the last sorted node, which is initialized to the first node,
and the node pointed to by P2 is the next one to be sorted.
When node 1 is the next node to be sorted, there is only one node (node 2) in the sorted list. Because the value 1 is less than the value in the list head, node 1 becomes the new head of the sorted list, and node 2 is linked to the next node of the previous node 1, which is node 4 (Figure(b)). Node 2 is still the last node in the sorted list, so it does not move P1, and only moves P2 to the next node of node 2.
The next node to be sorted is node 4. It traverses from the head node in order to find an appropriate location in the sorted list. Since the value 4 is greater than the value 2 in the last node of the sorted list, it is not necessary to relink nodes. Node 4 becomes the new last node of the sorted list, so it is pointed to by P1 (Figure(c)).
Now the next node to be sorted is node 3. It traverses from the head node again in order to find an appropriate location in the sorted list. Node 3 is linked between node 2 and node 4. Node 4 is still the last node in the sorted list. Since there are no nodes left after node 4, the whole list is sorted (Figure(d)).
When node 1 is the next node to be sorted, there is only one node (node 2) in the sorted list. Because the value 1 is less than the value in the list head, node 1 becomes the new head of the sorted list, and node 2 is linked to the next node of the previous node 1, which is node 4 (Figure(b)). Node 2 is still the last node in the sorted list, so it does not move P1, and only moves P2 to the next node of node 2.
The next node to be sorted is node 4. It traverses from the head node in order to find an appropriate location in the sorted list. Since the value 4 is greater than the value 2 in the last node of the sorted list, it is not necessary to relink nodes. Node 4 becomes the new last node of the sorted list, so it is pointed to by P1 (Figure(c)).
Now the next node to be sorted is node 3. It traverses from the head node again in order to find an appropriate location in the sorted list. Node 3 is linked between node 2 and node 4. Node 4 is still the last node in the sorted list. Since there are no nodes left after node 4, the whole list is sorted (Figure(d)).
The process to sort a list with four nodes. P1 points to the last node in the sorted list, and P2
points to the next node to be inserted into the sorted list, which always follows P1. (a) P1 is initialized to the first node, and P2 is initialized to the second one. (b) The node with value 2 is inserted into the sorted list. (c) The node with value 4 is inserted into the sorted list. (d) The node with value 3 is inserted into the sorted list.
The insert sort algorithm for lists can be implemented in C++, as shown in bellow
points to the next node to be inserted into the sorted list, which always follows P1. (a) P1 is initialized to the first node, and P2 is initialized to the second one. (b) The node with value 2 is inserted into the sorted list. (c) The node with value 4 is inserted into the sorted list. (d) The node with value 3 is inserted into the sorted list.
The insert sort algorithm for lists can be implemented in C++, as shown in bellow
C++ Code to Sort a List
else {
Because it has to scan O(n) nodes on the sorted list in order to find an appropriate location to insert a new node, it costs O(n2) time to sort a list with n nodes.
Test Cases:
www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community
void Sort(ListNode** pHead) {
if(pHead == NULL || *pHead == NULL)
return; ListNode* pLastSorted = *pHead;
ListNode* pToBeSorted = pLastSorted->m_pNext;
while(pToBeSorted != NULL) {
if(pToBeSorted->m_nValue < (*pHead)->m_nValue) {
pLastSorted->m_pNext = pToBeSorted->m_pNext;
pToBeSorted->m_pNext = *pHead;
*pHead = pToBeSorted;
}else {
ListNode* pNode = *pHead;
while(pNode != pLastSorted
&& pNode->m_pNext->m_nValue < pToBeSorted->m_nValue) {
pNode = pNode->m_pNext;
}
if(pNode != pLastSorted) {
pLastSorted->m_pNext = pToBeSorted->m_pNext;
pToBeSorted->m_pNext = pNode->m_pNext;
pNode->m_pNext = pToBeSorted;
}
else
pLastSorted = pLastSorted->m_pNext;
}
pToBeSorted = pLastSorted->m_pNext;
}
}
Because it has to scan O(n) nodes on the sorted list in order to find an appropriate location to insert a new node, it costs O(n2) time to sort a list with n nodes.
Test Cases:
-
Sort a list with multiple nodes, with/without duplicated values
-
The input list has only one node
-
The input head node of a list is NULL
