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 //www.geeksforgeeks.org/quicksort-on-singly-linked-list/
- Another java based implementation //www.fyears.org/2016/05/quicksort-in-array-and-linked-list.html
Video liên quan