Quick Sort of a Linked List

Quick Sort - Main Idea

1. Select a node (Probably Head node) as Pivot Node
2. Traverse through the remaining nodes to divide into two lists - one containing smaller or equal values and another containing larger values.
3. Recursively apply the sort algorithm to two smaller lists. As a base case, the recursive method will return the input when the input list is of size 1 or 0.
4. Merge First List, Pivot and Second List

Partition

Partition Method selects head node of given list as Pivot node. Based upon this pivot, the input list is divided into two smaller lists - First one with smaller or equal value and Second one with larger values.

Return Type

This method will return an array of Three Nodes - First one is head of first list, Second is Pivot node and the Third is the head of the second list.

	/**
	* Partitions the given linked list. Takes O(n) time and O(1) space
	*
	* @param head head node of the linked list to be partitioned
	* @return array of 3 elements, 1. head of first half 2. Pivot node and 3. head of second half
	*/
	public static ListNode[] partition(ListNode head) {
	ListNode pivot = head;
	ListNode node = head.next;
	pivot.next = null;
	ListNode firstHalfHead = null;
	ListNode secondHalfHead = null;
	while (node != null) {
	ListNode curr = node;
	node = node.next;
	if (curr.val <= pivot.val) {
	curr.next = firstHalfHead;
	firstHalfHead = curr;
	} else {
	curr.next = secondHalfHead;
	secondHalfHead = curr;
	}
	}
	return new ListNode[]{firstHalfHead, pivot, secondHalfHead};
	} // partition

view raw QuickSortLinkedList.java hosted with ❤ by GitHub

Sort Helper

sortHelper() is the recursive method that recursively sorts the smaller lists to finally return the sorted list.

Return Type

This method returns an array of two nodes - Head and Tail nodes of the Sorted List. They are required to ultimately merge the smaller lists and pivot.

	/**
	* Recursive helper method to sort the list. Recursively sorts the partitioned lists
	* and finally return the merged list which is sorted.
	* Average Case Time Complexity is O(nLogn) and Space Complexity is O(1)
	* @param head
	* @return
	*/
	public static ListNode[] sortHelper(ListNode head) {
	if (head == null || head.next == null) return new ListNode[]{head, head};
	ListNode[] partitions = partition(head);
	ListNode[] firstHeadTail = sortHelper(partitions[0]);
	ListNode[] secondHeadTail = sortHelper(partitions[2]);
	return merge(firstHeadTail, partitions[1], secondHeadTail);
	} // sortHelper

view raw QuickSortLinkedList.java hosted with ❤ by GitHub

Merge

merge() method merges the two smaller sorted list and the pivot.

Return Type

This method returns an array of two nodes - Head and Tail nodes of the Sorted List. They are required to ultimately merge the smaller lists and pivot.

	/**
	* Merges Two sorted lists and a pivot in between them. First list contains elements smaller than
	* or equal to pivot and Seconds list contains elements greater than pivot
	* Takes O(1) time and O(1) space
	*
	* @param firstHeadTail Array of Head and Tail Nodes of first sorted list
	* @param pivot Pivot node
	* @param secondHeadTail Array of Head and Tail Nodes of seconds sorted list
	* @return
	*/
	public static ListNode[] merge(ListNode[] firstHeadTail, ListNode pivot, ListNode[] secondHeadTail) {
	if (firstHeadTail[1] != null && secondHeadTail[1] != null) {
	firstHeadTail[1].next = pivot;
	pivot.next = secondHeadTail[0];
	return new ListNode[]{firstHeadTail[0], secondHeadTail[1]};
	} else if (firstHeadTail[1] != null) {
	firstHeadTail[1].next = pivot;
	return new ListNode[]{firstHeadTail[0], pivot};
	} else {
	pivot.next = secondHeadTail[0];
	return new ListNode[]{pivot, secondHeadTail[1]};
	}
	} // merge

view raw QuickSortLinkedList.java hosted with ❤ by GitHub

Complete Implementation

	/* File: SortLinkedList.java
	* Created: 8/21/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	//=======================================================================================
	/**
	* @author Sabbir Manandhar
	* manandharsabbir@gmail.com
	* @version 1.0
	*/
	public class QuickSortLinkedList {
	/**
	* main method
	* @param args
	*/
	public static void main(String[] args) {
	ListNode head = new ListNode(6);
	ListNode newNode = new ListNode(7);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(1);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(3);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(2);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(9);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(23);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(5);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(5);
	newNode.next = head;
	head = newNode;
	newNode = new ListNode(15);
	newNode.next = head;
	head = newNode;
	System.out.println(sort(head));
	} // main
	//-------------------------------------------------------------------------------------
	/**
	* Method to sort
	* @param head head of the list to sort
	* @return head of sorted list
	*/
	public static ListNode sort(ListNode head) {
	return sortHelper(head)[0];
	} // sort
	//-------------------------------------------------------------------------------------
	/**
	* Recursive helper method to sort the list. Recursively sorts the partitioned lists
	* and finally return the merged list which is sorted.
	* Average Case Time Complexity is O(nLogn) and Space Complexity is O(1)
	* @param head
	* @return
	*/
	public static ListNode[] sortHelper(ListNode head) {
	if (head == null || head.next == null) return new ListNode[]{head, head};
	ListNode[] partitions = partition(head);
	ListNode[] firstHeadTail = sortHelper(partitions[0]);
	ListNode[] secondHeadTail = sortHelper(partitions[2]);
	return merge(firstHeadTail, partitions[1], secondHeadTail);
	} // sortHelper
	//-------------------------------------------------------------------------------------
	/**
	* Merges Two sorted lists and a pivot in between them. First list contains elements smaller than
	* or equal to pivot and Seconds list contains elements greater than pivot
	* Takes O(1) time and O(1) space
	*
	* @param firstHeadTail Array of Head and Tail Nodes of first sorted list
	* @param pivot Pivot node
	* @param secondHeadTail Array of Head and Tail Nodes of seconds sorted list
	* @return
	*/
	public static ListNode[] merge(ListNode[] firstHeadTail, ListNode pivot, ListNode[] secondHeadTail) {
	if (firstHeadTail[1] != null && secondHeadTail[1] != null) {
	firstHeadTail[1].next = pivot;
	pivot.next = secondHeadTail[0];
	return new ListNode[]{firstHeadTail[0], secondHeadTail[1]};
	} else if (firstHeadTail[1] != null) {
	firstHeadTail[1].next = pivot;
	return new ListNode[]{firstHeadTail[0], pivot};
	} else {
	pivot.next = secondHeadTail[0];
	return new ListNode[]{pivot, secondHeadTail[1]};
	}
	} // merge
	//-------------------------------------------------------------------------------------
	/**
	* Partitions the given linked list. Takes O(n) time and O(1) space
	*
	* @param head head node of the linked list to be partitioned
	* @return array of 3 elements, 1. head of first half 2. Pivot node and 3. head of second half
	*/
	public static ListNode[] partition(ListNode head) {
	ListNode pivot = head;
	ListNode node = head.next;
	pivot.next = null;
	ListNode firstHalfHead = null;
	ListNode secondHalfHead = null;
	while (node != null) {
	ListNode curr = node;
	node = node.next;
	if (curr.val <= pivot.val) {
	curr.next = firstHalfHead;
	firstHalfHead = curr;
	} else {
	curr.next = secondHalfHead;
	secondHalfHead = curr;
	}
	}
	return new ListNode[]{firstHalfHead, pivot, secondHalfHead};
	} // partition
	} // QuickSortLinkedList
	//=======================================================================================
	class ListNode {
	ListNode next;
	int val;
	//-------------------------------------------------------------------------------------
	public ListNode(int data) {
	this.val = data;
	}
	//-------------------------------------------------------------------------------------
	public String toString() {
	StringBuilder sb = new StringBuilder();
	ListNode node = this;
	while (node != null) {
	sb.append(node.val + " ");
	node = node.next;
	}
	return sb.toString();
	} // toString
	} // ListNode

view raw QuickSortLinkedList.java hosted with ❤ by GitHub

---

---

---