algorithm - Optimal Quicksort for Single Linked List

Question

I am working on implementing a quicksort function to sort singly linked lists. What algorithm would I have to use to accomplish this ? For a linked list it would take worst case O(N) for each comparison, instead of the usual O(1) for arrays. So what would the worst case complexity be ?

To sum up, what modifications do I need to make to the quicksort algorithm to have an optimal sorting algorithm and what would be the worst case complexity of the algorithm ?

Thanks!

I have an implementation below:

public static SingleLinkedList quickSort(SingleLinkedList list, SLNode first, SLNode last)
{
    if (first != null && last != null)
    {
        SLNode p = partition(list, first, last) ;
        quickSort(list,first,p) ;
        quickSort(list,p.succ, last) ;
    }
    return list ;
}

public static SLLNode partition(SinlgleLinkedList list, SLNode first, SLNode last)
{

    SLNode p = first ;
    SLNode ptr = p.succ ;

    while (ptr!=null)
    {
        if (ptr.data.compareToIgnoreCase(p.data)<0)
        {
            String pivot = p.data ;
            p.data =  ptr.data ;
            ptr.data = p.succ.data ;
            p.succ.data = pivot ;
            p = p.succ ;
        }
        ptr = ptr.succ ;
    }
    return p ;
}

Answer 1

Mergesort is more natural to implement for linked lists, but you can do quicksort very nicely. Below is one in C I've used in several applications.

It's a common myth that you can't do Quicksort efficiently with lists. This just isn't true, although careful implementation is required.

To answer your question, the Quicksort algorithm for lists is essentially the same as for arrays. Pick a pivot (the code below uses the head of the list), partition into two lists about the pivot, then recursively sort those lists and append the results with pivot in the middle. What is a bit non-obvious is that the append operation can be done with no extra pass over the list if you add a parameter for a list to be appended as-is at the tail of the sorted result. In the base case, appending this list requires no work.

It turns out that if comparisons are cheap, mergesort tends to run a little faster because quicksort spends more time fiddling with pointers. However if comparisons are expensive, then quicksort often runs faster because it needs fewer of them.

If NODE *list is the head of the initial list, then you can sort it with

qs(list, NULL, &list);

Here is the sort code. Note a chunk of it is an optimization for already-sorted lists. This optimization can be deleted if these cases are infrequent.

void qs(NODE * hd, NODE * tl, NODE ** rtn)
{
    int nlo, nhi;
    NODE *lo, *hi, *q, *p;

    /* Invariant:  Return head sorted with `tl' appended. */
    while (hd != NULL) {

        nlo = nhi = 0;
        lo = hi = NULL;
        q = hd;
        p = hd->next;

        /* Start optimization for O(n) behavior on sorted and reverse-of-sorted lists */
        while (p != NULL && LEQ(p, hd)) {
            hd->next = hi;
            hi = hd;
            ++nhi;
            hd = p;
            p = p->next;
        }

        /* If entire list was ascending, we're done. */
        if (p == NULL) {
            *rtn = hd;
            hd->next = hi;
            q->next = tl;
            return;
        }
        /* End optimization.  Can be deleted if desired. */

        /* Partition and count sizes. */
        while (p != NULL) {
            q = p->next;
            if (LEQ(p, hd)) {
                p->next = lo;
                lo = p;
                ++nlo;
            } else {
                p->next = hi;
                hi = p;
                ++nhi;
            }
            p = q;
        }

        /* Recur to establish invariant for sublists of hd, 
           choosing shortest list first to limit stack. */
        if (nlo < nhi) {
            qs(lo, hd, rtn);
            rtn = &hd->next;
            hd = hi;        /* Eliminated tail-recursive call. */
        } else {
            qs(hi, tl, &hd->next);
            tl = hd;
            hd = lo;        /* Eliminated tail-recursive call. */
        }
    }
    /* Base case of recurrence. Invariant is easy here. */
    *rtn = tl;
}