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); }; |