Problem
Implement quick sort on singly linked list.
Solution
- Worst case time complexity of quick sort is O(n^2) but it’s 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.
* <p>
* Details - Choose the last node as pivot.
* Traverse and move the nodes with bigger value than pivot to the right of pivot.
* </p>
* @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