Optimal QuickSort for a Single Linked List

Question

I am working on implementing a quicksort function to sort individual lists. What algorithm should I use to achieve this? For a linked list for each comparison, you need the worst case O (N) instead of the usual O (1) for arrays. So what will be the hardest problem?

To summarize, what changes do I need to make the quicksort algorithm have an optimal sorting algorithm and what would be the worst 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 naturally implemented for linked lists, but you can do quicksort very nicely. Below is one of them that I used in several applications.

This is a common myth that you cannot efficiently execute Quicksort with lists. This is simply not true, although careful implementation is required.

To answer your question, the Quicksort algorithm for lists is essentially the same as for arrays. Select the bar (the code below uses the head of the list), split into two lists about the code, then sort these lists recursively and add the results with the center in the middle. What is a little non-obvious is that the add operation can be performed without additional passing over the list if you add an option for the list to be added as-is at the tail of the sorted result. In the basic case, adding this list does not require work.

It turns out that if the comparison is cheap, the merge is usually a little faster, because quicksort spends more time looking for pointers. However, if comparisons are expensive, quicksort often works faster because it requires less.

If NODE *list is the head of the original list, you can sort it using

 qs(list, NULL, &list); 

Here is the sort code. Note that this is an optimization for already sorted lists. This optimization can be removed 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 expected behavior of O (n * log (n)). The trick is simple - put the nodes in an array, sort the array of nodes, rearrange them in the correct order.

Answer 3

Here is the Java implementation. He uses the head as a rod. This can be further improved if you do not scan the left sublist before adding the right sublist, but it works. This is also O (nLogn).

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