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;
}

Answer 2

You can use quicksort and not lose the O(n*log(n)) expected behaviour. The trick is simple — the nodes into the array, sort the array of nodes, relink them in the correct order.

Answer 3

Here is a java implementation. It uses the head as the pivot. This can further be improved by avoiding the scanning of the left sublist before appending the right sublist, but it works. This is O(nLogn) too.

public class QuickSortLinkedList {

 public ListNode sortList(ListNode head) {

        //Base Case
        if(head == null || head.next == null)
            return head;
        //Partition Strategy
        //Chose first element as pivot and move all elements smaller than the pivot at the end of LL
        //So the order will be pivot, elements smaller than or equal to pivot, elements larger than pivot
        //Example: 9,13,10,6,9,8,11 => 9,13,10,9,11,6,8  and the method will return a pointer to 11
        ListNode partitionedElement = partition(head);

        //The elements to the right of pivot were all smaller than pivot after partioned
        //Example: LeftPartition  = 6->8->null
        ListNode leftPartition = partitionedElement.next;

        //The elements to the left of pivot were all large , so they go in right partition
        //Example: rightPartition = 9->13->10->9->11->null
        ListNode rightPartition = head;
        partitionedElement.next = null;

        //But there can be edge cases
        //Example: 3,5,3,4,5-null => after partition , list is unchanged and last element 5 is returned
        //in this case leftPartition: 3->null and rightPartition 5,3,4,5-null
        if(leftPartition == null){
            leftPartition = head;
            rightPartition = head.next;
            head.next =null;
        }

        //Now Recursively sort
        rightPartition = sortList(rightPartition);
        leftPartition = sortList(leftPartition);

        //After sorting append rightPartition to leftPartition
        ListNode iterator = leftPartition;
        while(iterator.next!=null)
            iterator = iterator.next;
        iterator.next = rightPartition;

        return leftPartition;
    }

    private ListNode partition(ListNode head){
     //Base case
     if(head.next.next == null){

         if(head.next.val>head.val)
            return head.next;
         else
         return head;
     } 

    else{    
        ListNode i = head.next;
        ListNode pivot = head;
        ListNode lastElementSwapped = (pivot.next.val>=pivot.val)?pivot.next:pivot;

        while(i!=null && i.next !=null){

            if(i.next.val >= pivot.val){
                if(i.next == lastElementSwapped.next){
                    lastElementSwapped = lastElementSwapped.next;
                }
                else{
                    ListNode temp = lastElementSwapped.next;
                    lastElementSwapped.next = i.next;
                    i.next = i.next.next;
                    lastElementSwapped = lastElementSwapped.next;
                    lastElementSwapped.next = temp;
                }
            }

            i = i.next;

        }
        return lastElementSwapped;
    }

  }
}

Answer 4

You can use this algorithm:

• Choose the head node as pivot node.
• The left partition starts with the pivot node, which will remain its tail
• The right partition starts empty
• For each node: pre-pend it to either the left or right partition list, setting its next reference to the current head of that partition, and making it its new head.
• Since the pivot element is the tail node of the left partition, set its next reference to null, so to really terminate that list there.
• Apply recursion on the left and right partition, returning its potentially modified head references.
• Tie the two sorted sublists together. As the tail node of the left partition is guaranteed to remain there and was the pivot node, set its next reference to the head of the second, sorted partition.
• Return the head of the sorted list.

Recursion stops when the base is encountered, which is when the list has fewer than 2 nodes.

This has an average time complexity of O(nlogn). The worst time complexity is O(n²). For instance, when the list is already sorted it will suffer this time complexity.

Here is a singly linked list implementation in Python with a quick_sort method:

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.next = nxt

    def __iter__(self):
        curr = self
        while curr:
            node = curr
            curr = curr.next
            yield node

    def values(self):
        return (node.data for node in self)

    def partition(self):
        nodes = iter(self) # All nodes headed by this node
        next(nodes)  # Skip self
        left = self   # Left partition always has pivot node as its tail
        pivotvalue = self.data
        right = None
        for curr in nodes:  # Remaining nodes
            # Prefix the current node to the relevant partition
            if curr.data < pivotvalue:
                curr.next = left
                left = curr
            else:
                curr.next = right
                right = curr
        self.next = None  # Terminate the left partition
        return left, right 
        
    def quick_sort(self):
        if not self.next:  # Base case: one node only
            return self
        left, right = self.partition()
        # Left partition has at least one node (the pivot node, which remains its tail)
        left = left.quick_sort()
        # Right partition could be empty 
        if right:
            right = right.quick_sort()
        self.next = right  # Chain the two sorted partitions
        return left

    def is_sorted(self):
        values = self.values()
        prev = next(values)
        for data in values:
            if data < prev:
                return False
            prev = data
        return True


class LinkedList:
    def __init__(self, *values):
        self.head = None
        self.prefix(*values)
    
    def prefix(self, *values):
        for data in reversed(values):
            self.head = Node(data, self.head)
            
    def values(self):
        if self.head:
            return self.head.values()

    def quick_sort(self):
        self.head = self.head and self.head.quick_sort()

    def is_sorted(self):
        return self.head is not None and self.head.is_sorted()

Here is some code to test this implementation repeatedly with shuffled lists of 20 values:

from random import shuffle

values = list(range(20))
for _ in range(100):
    shuffle(values)
    linkedlist = LinkedList(*values)
    print("Shuffled:", *linkedlist.values())
    linkedlist.quick_sort()
    print("Sorted:", *linkedlist.values())
    if not linkedlist.is_sorted():  # Test for failure
        raise ValueError("not sorted!")