Uncategorized

Quicksort implementation using Linked List

About QuickSort

Wikipedia QuickSort definition.

General idea revolves around partitioning a list where values less than pivot go into left list while greater than go into right list.
Pivot here is the first item of the passed in list. We apply this recursively to the sublists them merge left+pivot+right.

CPP Code

First of all not a cpp developer so if you can improve this them post a comment with suggestions.

 
template <class Record>
Node<Record> * List<Record>::quick_sort_recursive(Node<Record>* list)
{
	//Base case : list  is NULL
	if(list ==  NULL){
		return NULL;
	}
 
	//We choose first entry in the list as the pivot node
	Node<Record> * pivotNode = new Node<Record>();
	pivotNode->entry=list->entry;
	Record pivot = pivotNode->entry;
 
	Node<Record> *tmp=list->next;
	Node<Record> *leftHead=NULL;
	Node<Record> *rightHead=NULL;
 
	Node<Record> *leftTail=NULL;
	Node<Record> *rightTail=NULL;
 
	//Partition the list into left/right sublists
	while(tmp != NULL){
		Node<Record> *entryNode=new Node<Record>();
		entryNode->entry = tmp->entry;
		entryNode->next = NULL;
		if(tmp->entry < pivot){
			if(leftTail == NULL){
				leftTail = entryNode;
				leftHead=entryNode;
			}else{
				leftTail->next=entryNode;
				leftTail=leftTail->next;
			}
		}
		else{
			if(rightTail == NULL){
				rightTail = entryNode;
				rightHead=entryNode;
			}else{
				rightTail->next=entryNode;
				rightTail=rightTail->next;
			}
		}
		tmp = tmp->next;
	}
 
	//Recursively subdivide the left / right list
	leftHead  = quick_sort_recursive(leftHead);
	rightHead = quick_sort_recursive(rightHead);
 
	//Combine left+pivot+right
	Node<Record> * mergedHead=NULL;
	Node<Record> * mergedTail=NULL;
 
	Node<Record> *tmpNode=leftHead;
	while(tmpNode){
		Node<Record> *new_node=new Node<Record>();
		new_node->entry=tmpNode->entry;
		if(mergedTail == NULL){
			mergedTail = new_node;
			mergedHead= new_node;
		}else{
			mergedTail->next= new_node;
			mergedTail=mergedTail->next;
		}
		tmpNode=tmpNode->next;
	}
	//Pivot point
	if(mergedTail == NULL){
		mergedTail = pivotNode;
		mergedHead = pivotNode;
	}else{
		mergedTail->next=pivotNode;
		mergedTail=mergedTail->next;
	}
	//Right sublist
	tmpNode=rightHead;
	while(tmpNode){
		Node<Record> *new_node=new Node<Record>();
		new_node->entry=tmpNode->entry;
		mergedTail->next=new_node;
		mergedTail=mergedTail->next;
		tmpNode=tmpNode->next;
	}
 
	return mergedHead;
}
 
 
 
template <class Node_entry>
struct Node {
//  data members
   Node_entry entry;
   Node<Node_entry> *next;
//  constructors
   Node();
   Node(Node_entry, Node<Node_entry> *link = NULL);
};

Leave a Reply

Your email address will not be published. Required fields are marked *

* Copy This Password *

* Type Or Paste Password Here *