Quick sort is one of the most widely used sorting algorithm due to its time complexity of O(n log n). It’s preferred over merge sort as it’s space efficient. Like merge sort, quick sort also follows divide and conquer strategy. Idea is to decide on the pivot and move the elements bigger than the pivot to its right ensuring that the position of pivot is fixed in the sorted array. This forms 2 partitions – Partition left to the pivot and partition right to the pivot. Same procedure is repeated for left and the right partitions till the size of the partition is reduced to one element. Key to the quick sort is the partitioning algorithm.
Java implementation of quick sort on singly linked list.
Quick sort
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);
}
}