Can QuickSort be performed on a linked list?

Problem

Implement quick sort on singly linked list.

Solution

• Worst case time complexity of quick sort is O(n^2) but its rare.
• Quick sort follows divide and conquer approach.
• Quick sort is preferred over merge sort as quick sort is an in-place algorithm (meaning, no additional memory space required).
• Java based un-optimized implementation shown below.

package com.computepatterns.problemsolving.linkedlist; /** * Abstract implementation of singly linked list */ public class AbstractSinglyLinkedList { private Node start; public void setStart(Node start) { this.start = start; } /** * Creates string representing the sequence of the content of the list delimite by coma. */ public String createStringRepresentation(Node start){ Node currentNode = start; StringBuilder toPrint = new StringBuilder(); while(null != currentNode){ toPrint.append(currentNode.getValue() + ","); currentNode = currentNode.next; } return toPrint.toString(); } /** * Represents nodes in the linked list. */ protected static class Node{ private int value; private Node next; public Node(int value) { this.value = value; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Node node = (Node) o; return value == node.value && com.google.common.base.Objects.equal(next, node.next); } @Override public int hashCode() { return com.google.common.base.Objects.hashCode(value, next); } public int getValue() { return value; } Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } } package com.computepatterns.problemsolving.linkedlist; /** * Quick sort implementation for singly linked list. * Worst case complexity - O(n^2). Worst case is rare. * Preferred over merge sort as this is in-place sorting (requires no additional memory). */ public class QuickSortLinkedList extends AbstractSinglyLinkedList { public Node quickSort(Node start, Node end){ /* Exist condition */ // If the list contains one or less node, return the start node itself. if(null == start || null == start.getNext() || start == end){ return start; } /* Partition the list */ // Result contains start/end of left and right segments and the pivot. Node[] result = partition(start, end); /* Recur the left side */ Node resultLeft = null; //Start of left result. if(null != result[0]) { resultLeft = quickSort(result[0], result[1]); } /* Recur the right side */ Node resultRight = null; // Start of right result. if(null != result[3]){ resultRight = quickSort(result[3], result[4]); } /* Connect the pivot to the start of right segmen */ if(resultRight !=null) { result[2].setNext(resultRight); } /* Return start of the list */ if(null == resultLeft){ // If left segment has nothing, return pivot. return result[2]; }else{ // Else return the start of left. return resultLeft; } } /** * Partitioning. *

* Details - Choose the last node as pivot. * Traverse and move the nodes with bigger value than pivot to the right of pivot. *

* @param start * @param end * @return Array of nodes[Start of left, end of left, pivot, start of right, end of right] */ private Node[] partition (Node start, Node end){ /* Choose a pivot */ // We are not moving pivot but the other nodes. Node pivot = end; /* Define the required pointers */ // Tail points to the end of new list Node tail = end; // Start of newly arranged list Node newStart = null; // Iteration pointers Node current = start; Node previous = null; /* Iterate and move nodes */ // Iterate the original list till the end. boolean isFirstNodeWithoutMove = true; while(null != current && end != current){ Node next = current.getNext(); // For nodes with value grater than pivot move to the right of pivot. if(current.getValue() > pivot.getValue()){ // Move the current node to the end of the list. moveNodeToEnd(current, previous, tail); // Advance tail. tail = tail.getNext(); }else{ if(isFirstNodeWithoutMove){ newStart = current; isFirstNodeWithoutMove = false; } // Advance iteration pointers. if(null != previous){ previous.setNext(current); } previous = current; } current = next; } /* Prepare result for returning */ Node[] result = new Node[5]; result[0] = newStart; result[1] = previous; result[2] = pivot; result[3] = pivot.getNext(); result[4] = tail; return result; } private void moveNodeToEnd(Node current, Node previous, Node tail) { if(null != previous){ previous.setNext(current.getNext()); } current.setNext(null); tail.setNext(current); } }

Unit test

package com.computepatterns.problemsolving.linkedlist; import static org.junit.Assert.assertEquals; import org.junit.Test; /** * Unit test for quick sort implementation on linked list. */ public class QuickSortLinkedListTest { @Test public void testQuickSort_case1() throws Exception { QuickSortLinkedList linkedList = new QuickSortLinkedList(); QuickSortLinkedList.Node node1 = new QuickSortLinkedList.Node(40); QuickSortLinkedList.Node node2 = new QuickSortLinkedList.Node(3); QuickSortLinkedList.Node node3 = new QuickSortLinkedList.Node(10); QuickSortLinkedList.Node node4 = new QuickSortLinkedList.Node(20); QuickSortLinkedList.Node node5 = new QuickSortLinkedList.Node(7); QuickSortLinkedList.Node node6 = new QuickSortLinkedList.Node(4); node1.setNext(node2); node2.setNext(node3); node3.setNext(node4); node4.setNext(node5); node5.setNext(node6); linkedList.setStart(node1); // Before reversing. System.out.println(linkedList.createStringRepresentation(node1)); // Find middle element. QuickSortLinkedList.Node result = linkedList.quickSort(node1, node6); // After reversing. String stringRepresentation = linkedList.createStringRepresentation(result); System.out.println(stringRepresentation); assertEquals("3,4,7,10,20,40,", stringRepresentation); } @Test public void testQuickSort_case2() throws Exception { QuickSortLinkedList linkedList = new QuickSortLinkedList(); QuickSortLinkedList.Node node1 = new QuickSortLinkedList.Node(40); QuickSortLinkedList.Node node2 = new QuickSortLinkedList.Node(30); QuickSortLinkedList.Node node3 = new QuickSortLinkedList.Node(10); QuickSortLinkedList.Node node4 = new QuickSortLinkedList.Node(20); node1.setNext(node2); node2.setNext(node3); node3.setNext(node4); linkedList.setStart(node1); // Before reversing. System.out.println(linkedList.createStringRepresentation(node1)); // Find middle element. QuickSortLinkedList.Node result = linkedList.quickSort(node1, node4); // After reversing. String stringRepresentation = linkedList.createStringRepresentation(result); System.out.println(stringRepresentation); assertEquals("10,20,30,40,", stringRepresentation); } }

References

• CPP implementation http://www.geeksforgeeks.org/quicksort-on-singly-linked-list/
• Another java based implementation https://www.fyears.org/2016/05/quicksort-in-array-and-linked-list.html