Stable Quicksort With Linked List

Question

I am trying to make a stable implementation of quicksort using linked lists, and for some reason this code is crashing. It seems to get to the second iteration of the while loop in partition before it crashes.

Basically, I'm using the head as a pivot point and anything less goes in a new linked list and anything greater than the pivot goes in a new linked list as well. This is called recursively and then at the end they are combined.

    class Node
    {
    public:
        Node* next;
        int key;
        int key2;

        Node()
        {
            next = NULL;
        }
    };

    void fillRandom(Node*& root, int length)
    {
       if(length != 0){
            root->key = rand()%10;
            root->next = new Node;
            fillRandom(root->next, length-1);
        }
    }

    void partitionLL(Node*& lessThan, Node*& greaterThan, Node*& root)
    {
        Node* lessThanTemp = lessThan; Node* greaterThanTemp = greaterThan;
        Node* temp = root;

        while(temp->next != NULL)
        {
            if(temp->key > root->key){
                greaterThanTemp = temp;
                greaterThanTemp->next = new Node;
                greaterThanTemp = greaterThanTemp->next;
            }else{
                lessThanTemp = temp;
                lessThanTemp->next = new Node;
                lessThanTemp = lessThanTemp->next;
            }
            temp = temp->next;
        }
    }

    void quickSort(Node* root)
    {
        if(root->next != NULL){//i.e. theres only two nodes in the list
            Node* lessThan = new Node; Node* greaterThan = new Node;
            partitionLL(lessThan, greaterThan, root);
            quickSort(lessThan);
            quickSort(greaterThan);
        }else{
            return;
        }
    }

    int main()
    {
        int length = 15;
        Node* root = new Node;

        fillRandom(root, length);
        quickSort(root);
    }

Answer 1

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.