We have already seen in-detail about the quick sort algorithm and its iterative as well as recursive implementation on arrays. In this example we will see how we can use quick sort on linked list.
Example
Input: 30 -> 3 -> 4 -> 20 -> 5 -> null Output: 3 -> 4 -> 5 -> 20 -> 30 -> null
Quick sort using linked list
The most challenging aspect in soring a linked list is working with pointers to swap the elements position.
Partition
We consider last element as a pivot while partitioning. We traverse through the current list and if a node has value greater than pivot, we move it after tail. If the node has smaller value, we keep it at its current position.
const partitionLast = (start, end) => { //Base case if(start === end || start === null || end === null){ return start; } let pivot_prev = start; let curr = start; let pivot = end.element; // iterate till one before the end, // no need to iterate till the end // because end is pivot while(start !== end){ if(start.element < pivot){ // keep tracks of last modified item pivot_prev = curr; let temp = curr.element; curr.element = start.element; start.element = temp; curr = curr.next; } start = start.next; } // swap the position of curr i.e. // next suitable index and pivot let temp = curr.element; curr.element = pivot; end.element = temp; // return one previous to current // because current is now pointing to pivot return pivot_prev; }
Performing sort
We first call the partition function which places the pivot at its correct position and returns pivot. Once the pivot is placed at its position, we find the tail node of left side (list before the pivot) and recur for left list and then recur for the right list.
const sort = (start, end) => { if(start === end){ return; } // split list and partion recurse let pivot_prev = partitionLast(start, end); sort(start, pivot_prev); // if pivot is picked and moved to the start, // that means start and pivot is same // so pick from next of pivot if(pivot_prev !== null && pivot_prev === start){ sort(pivot_prev.next, end); } // if pivot is in between of the list, // start from next of pivot, // since we have pivot_prev, so we move two nodes else if(pivot_prev !== null && pivot_prev.next !== null){ sort(pivot_prev.next.next, end); } }
Input: let list = new linkedlist(); list.append(30); list.append(3); list.append(4); list.append(20); list.append(5); //Move to the end (tail node) let end = list.getHead(); while(end.next != null){ end = end.next; } //Get the start let start = list.getHead(); //Sort the list sort(start , end); //Print the sorted list while(start){ console.log(start.element); start = start.next; } Output: 3 4 5 20 30
Time complexity: O(nlogn).
Space complexity: O(logn).