You idea is founded (building two linked lists). Its the detachment and reattachment code that is lacking. When dealing with linked lists the first thing to remember is it is rare that you ever need to allocate new nodes when doing rearrangement. You use the nodes you're given. That is what they're there for. All your algorithm should be doing is simply rearranging the pointers within.
The following does precisely that. Once the list is allocated no new nodes are needed. The algorithm apart from that is the same idea as yours:
- Use the head node as the pivot value. Detach it from the list
- Enumerate the remainder of the list tacking nodes into one of two lists along the way. Note the code for doing the movement from one list to another adds the nodes to the ends of their respective lists.
- When finished, you have two lists and a lonesome pivot node all on its own. Terminate both lists and recurse.
- Once the recursion returns seek to the end of the left-side list. That is the place where the pivot node is tacked, then the right-side list is joined to that.
The code is below. I strongly suggest walking through it in a debugger:
#include <iostream>
#include <iterator>
#include <algorithm>
#include <random>
struct Node
{
Node* next;
int key;
int key2;
Node( int key, int key2 )
: key(key), key2(key2), next()
{}
};
Node * createList(size_t N)
{
std::random_device rd;
std::mt19937 rng(rd());
std::uniform_int_distribution<> dist(1,10);
Node *root = nullptr;
Node **pp = &root;
for (int i=0; i<N; ++i)
{
*pp = new Node(dist(rng), i+1);
pp = &(*pp)->next;
}
return root;
}
void freeList(Node *& root)
{
while (root)
{
Node *tmp = root;
root = tmp->next;
delete tmp;
}
}
void printList(const Node* root)
{
for (;root;root = root->next)
std::cout << root->key << '(' << root->key2 << ") ";
std::cout << '\n';
}
// quicksort a linked list.
void quickSort(Node *&root)
{
// trivial lists are just returned immediately
if (!root || !(root->next))
return;
Node *lhs = nullptr, **pplhs = &lhs;
Node *rhs = nullptr, **pprhs = &rhs;
Node *pvt = root;
root = root->next;
pvt->next = nullptr;
while (root)
{
if (root->key < pvt->key)
{
*pplhs = root; // tack on lhs list end
pplhs = &(*pplhs)->next;
}
else
{
*pprhs = root; // tack on rhs list end
pprhs = &(*pprhs)->next;
}
root = root->next;
}
// terminate both list. note that the pivot is still
// unlinked, and will remain so until we merge
*pplhs = *pprhs = nullptr;
// invoke on sublists.
quickSort(lhs);
quickSort(rhs);
// find end of lhs list, slip the pivot into position, then
// tack on the rhs list.
while (*pplhs)
pplhs = &(*pplhs)->next;
*pplhs = pvt;
pvt->next = rhs;
// set final output
root = lhs;
}
int main()
{
Node *root = createList(20);
printList(root);
quickSort(root);
printList(root);
freeList(root);
return 0;
}
Output (varies)
6(1) 7(2) 1(3) 10(4) 8(5) 10(6) 4(7) 7(8) 2(9) 9(10) 1(11) 8(12) 10(13) 8(14) 6(15) 9(16) 8(17) 2(18) 8(19) 9(20)
1(3) 1(11) 2(9) 2(18) 4(7) 6(1) 6(15) 7(2) 7(8) 8(5) 8(12) 8(14) 8(17) 8(19) 9(10) 9(16) 9(20) 10(4) 10(6) 10(13)
The number in parens is the original order of the nodes in the original list. Note that I specifically chose a small random pool to choose from so as to experience lots of equal-keys, thereby demonstrating the sort is stable; like-keys preserve their original list ordering. For example, there were five 8
values in the original list. After sorting their sequence is:
8(5) 8(12) 8(14) 8(17) 8(19)
This is intentional, and accomplished by ensuring when we moved items to the split-lists we always tacked them on the ends.
Anyway, I hope it helps.