Quick Sort on Doubly Linked List is discussed here. Quick Sort on Singly linked list was given as an exercise. Following is C++ implementation for same. The important things about implementation are, it changes pointers rather swapping data and time complexity is same as the implementation for Doubly Linked List.
In partition(), we consider last element as pivot. We traverse through the current list and if a node has value greater than pivot, we move it after tail. If the node has smaller value, we keep it at its current position.
In QuickSortRecur(), we first call partition() which places pivot at correct position and returns pivot. After pivot is placed at correct position, we find tail node of left side (list before pivot) and recur for left list. Finally, we recur for right list.
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20for%20Quick%20Sort%20on%20Singly%20Linled%20List%0A%23include%20%3Ciostream%3E%0A%23include%20%3Ccstdio%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20a%20node%20of%20the%20singly%20linked%20list%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*next%3B%0A%7D%3B%0A%20%0A%2F*%20A%20utility%20function%20to%20insert%20a%20node%20at%20the%20beginning%20of%20linked%20list%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%20new%20node%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20to%20print%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%20%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20the%20last%20node%20of%20the%20list%0Astruct%20node%20*getTail(struct%20node%20*cur)%0A%7B%0A%20%20%20%20while%20(cur%20!%3D%20NULL%20%26%26%20cur-%3Enext%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20cur%20%3D%20cur-%3Enext%3B%0A%20%20%20%20return%20cur%3B%0A%7D%0A%20%0A%2F%2F%20Partitions%20the%20list%20taking%20the%20last%20element%20as%20the%20pivot%0Astruct%20node%20*partition(struct%20node%20*head%2C%20struct%20node%20*end%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20struct%20node%20**newHead%2C%20struct%20node%20**newEnd)%0A%7B%0A%20%20%20%20struct%20node%20*pivot%20%3D%20end%3B%0A%20%20%20%20struct%20node%20*prev%20%3D%20NULL%2C%20*cur%20%3D%20head%2C%20*tail%20%3D%20pivot%3B%0A%20%0A%20%20%20%20%2F%2F%20During%20partition%2C%20both%20the%20head%20and%20end%20of%20the%20list%20might%20change%0A%20%20%20%20%2F%2F%20which%20is%20updated%20in%20the%20newHead%20and%20newEnd%20variables%0A%20%20%20%20while%20(cur%20!%3D%20pivot)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(cur-%3Edata%20%3C%20pivot-%3Edata)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20First%20node%20that%20has%20a%20value%20less%20than%20the%20pivot%20-%20becomes%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20the%20new%20head%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20((*newHead)%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(*newHead)%20%3D%20cur%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20cur%3B%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20cur%20%3D%20cur-%3Enext%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%20%2F%2F%20If%20cur%20node%20is%20greater%20than%20pivot%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Move%20cur%20node%20to%20next%20of%20tail%2C%20and%20change%20tail%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(prev)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prev-%3Enext%20%3D%20cur-%3Enext%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20struct%20node%20*tmp%20%3D%20cur-%3Enext%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20cur-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20tail-%3Enext%20%3D%20cur%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20tail%20%3D%20cur%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20cur%20%3D%20tmp%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20the%20pivot%20data%20is%20the%20smallest%20element%20in%20the%20current%20list%2C%0A%20%20%20%20%2F%2F%20pivot%20becomes%20the%20head%0A%20%20%20%20if%20((*newHead)%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20(*newHead)%20%3D%20pivot%3B%0A%20%0A%20%20%20%20%2F%2F%20Update%20newEnd%20to%20the%20current%20last%20node%0A%20%20%20%20(*newEnd)%20%3D%20tail%3B%0A%20%0A%20%20%20%20%2F%2F%20Return%20the%20pivot%20node%0A%20%20%20%20return%20pivot%3B%0A%7D%0A%20%0A%20%0A%2F%2Fhere%20the%20sorting%20happens%20exclusive%20of%20the%20end%20node%0Astruct%20node%20*quickSortRecur(struct%20node%20*head%2C%20struct%20node%20*end)%0A%7B%0A%20%20%20%20%2F%2F%20base%20condition%0A%20%20%20%20if%20(!head%20%7C%7C%20head%20%3D%3D%20end)%0A%20%20%20%20%20%20%20%20return%20head%3B%0A%20%0A%20%20%20%20node%20*newHead%20%3D%20NULL%2C%20*newEnd%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F%2F%20Partition%20the%20list%2C%20newHead%20and%20newEnd%20will%20be%20updated%0A%20%20%20%20%2F%2F%20by%20the%20partition%20function%0A%20%20%20%20struct%20node%20*pivot%20%3D%20partition(head%2C%20end%2C%20%26newHead%2C%20%26newEnd)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20pivot%20is%20the%20smallest%20element%20-%20no%20need%20to%20recur%20for%0A%20%20%20%20%2F%2F%20the%20left%20part.%0A%20%20%20%20if%20(newHead%20!%3D%20pivot)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Set%20the%20node%20before%20the%20pivot%20node%20as%20NULL%0A%20%20%20%20%20%20%20%20struct%20node%20*tmp%20%3D%20newHead%3B%0A%20%20%20%20%20%20%20%20while%20(tmp-%3Enext%20!%3D%20pivot)%0A%20%20%20%20%20%20%20%20%20%20%20%20tmp%20%3D%20tmp-%3Enext%3B%0A%20%20%20%20%20%20%20%20tmp-%3Enext%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Recur%20for%20the%20list%20before%20pivot%0A%20%20%20%20%20%20%20%20newHead%20%3D%20quickSortRecur(newHead%2C%20tmp)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Change%20next%20of%20last%20node%20of%20the%20left%20half%20to%20pivot%0A%20%20%20%20%20%20%20%20tmp%20%3D%20getTail(newHead)%3B%0A%20%20%20%20%20%20%20%20tmp-%3Enext%20%3D%20%20pivot%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Recur%20for%20the%20list%20after%20the%20pivot%20element%0A%20%20%20%20pivot-%3Enext%20%3D%20quickSortRecur(pivot-%3Enext%2C%20newEnd)%3B%0A%20%0A%20%20%20%20return%20newHead%3B%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20for%20quick%20sort.%20This%20is%20a%20wrapper%20over%20recursive%0A%2F%2F%20function%20quickSortRecur()%0Avoid%20quickSort(struct%20node%20**headRef)%0A%7B%0A%20%20%20%20(*headRef)%20%3D%20quickSortRecur(*headRef%2C%20getTail(*headRef))%3B%0A%20%20%20%20return%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20struct%20node%20*a%20%3D%20NULL%3B%0A%20%20%20%20push(%26a%2C%205)%3B%0A%20%20%20%20push(%26a%2C%2020)%3B%0A%20%20%20%20push(%26a%2C%204)%3B%0A%20%20%20%20push(%26a%2C%203)%3B%0A%20%20%20%20push(%26a%2C%2030)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Linked%20List%20before%20sorting%20%5Cn%22%3B%0A%20%20%20%20printList(a)%3B%0A%20%0A%20%20%20%20quickSort(%26a)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Linked%20List%20after%20sorting%20%5Cn%22%3B%0A%20%20%20%20printList(a)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”c++” highlight=”” provider=”manual”/]
Output:
Linked List before sorting
30 3 4 20 5
Linked List after sorting
3 4 5 20 30
[ad type=”banner”]