/* ************************ Written by: bornToCode() ************************ This was an assignment in my data structures & algorithms class. The assignement was to implement a quicksort for a singly linked list. Our list read in a file of 2000 entries, sorted them, and then did the same for another 200,000 entries and recorded the elapsed time. This version has been watered down for Sololearn, and getting the elapsed time with a clock_t object didnt seem to work. */ #include #include #include #include using namespace std; /************************************** Node Class ***************************************/ template class Node { public: Record data; Node *next; Node(); Node(Record, Node* = NULL); private: }; template Node::Node() : next(NULL) {} template Node::Node(Record data, Node *next) : data(data), next(next) {} /************************************** List Class ***************************************/ template class List { public: List(); List(const List &); ~List(); bool isEmpty() const; bool isFull() const; int size() const; void clear(); void insert(int, const Record &); void remove(int, Record &); void retrieve(int, Record &); void replace(int, const Record &); void traverse(void(*)(Record &)); List operator =(const List &); protected: Node *head; int count; Node* getNode(int) const; }; template List::List() : count(0), head(NULL) {} //copy constructor template List::List(const List &right) { count = right.count; Node *newNode, *oldNode = right.head; if(oldNode == NULL) head = NULL; else { newNode = head = new Node(oldNode->data); while(oldNode->next) { oldNode = oldNode->next; newNode->next = new Node(oldNode->data); newNode = newNode->next; } } } template List::~List() { clear(); } template bool List::isEmpty() const { return count == 0; } template bool List::isFull() const { return false; } template int List::size() const { return count; } template void List::clear() { while(!isEmpty()) { Record data; remove(0, data); } head = NULL; } template Node* List::getNode(int position) const { Node *target = head; for(int i = 0; i < position; i++) { target = target->next; } return target; } template void List::insert(int position, const Record &data) { assert(position >= 0); Node *previous, *newNode, *following; if(position > 0) { assert(position < count); previous = getNode(position - 1); following = previous->next; } else { following = head; } newNode = new Node(data, following); if(position == 0) head = newNode; else previous->next = newNode; count++; } template void List::remove(int position, Record &data) { assert(position >= 0 && count > 0); Node *prev, *target; if(position > 0) { assert(position < count); prev = getNode(position - 1); target = prev->next; prev->next = target->next; } else { target = head; head = head->next; } data = target->data; delete target; count--; } template void List::retrieve(int position, Record &data) { assert(position >= 0 && count > 0); Node *target; if(position > 0) { assert(position < count); target = getNode(position); } else target = head; data = target->data; } template void List::replace(int position, const Record &data) { assert(position >= 0 && count > 0); Node *target; if(position > 0) { assert(position < count); target = getNode(position); } else target = head; target->data = data; } template void List::traverse(void(*visit)(Record &data)) { assert(count > 0); Node *current = head; for(int i = 0; i < count; i++) { (*visit)(current->data); current = current->next; } } template List List::operator = (const List &right) { List newList(right); clear(); count = newList.count; head = newList.head; newList.count = 0; newList.head = NULL; return *this; } /************************************** SortableList Class ***************************************/ template class SortableList : public List { public: void quickSort(); private: void recursiveQuickSort(Node*&, Node*&); Node* partition(Node*&, Node*&); }; template void SortableList::quickSort() { Node *tail; recursiveQuickSort(this->head, tail); } template void SortableList::recursiveQuickSort(Node *&subList, Node *&tail) { if(subList != NULL && subList->next != NULL) { Node *pivot, *tail1,*tail2; Node *highList = partition(subList, pivot); recursiveQuickSort(subList, tail1); recursiveQuickSort(highList, tail2); //link lowList, pivot, and highList if(subList == NULL) { subList = pivot; pivot->next = highList; tail = tail2; } else if(highList == NULL) { tail1->next = tail = pivot; } else { tail1->next = pivot; pivot->next = highList; tail = tail2; } } else if(subList == NULL) { tail = NULL; } else if(subList->next == NULL) { tail = subList; } } template Node* SortableList::partition(Node *&subList, Node *&pivot) { Node *current, *lowHead, *highHead; lowHead = highHead = NULL; if((pivot = subList) == NULL) return NULL; current = pivot->next; //separate pivot from sublist pivot->next = NULL; while (current != NULL) { Node *newNode = current; current = current->next; if(newNode->data < pivot->data) { if(lowHead == NULL) newNode->next = NULL; else newNode->next = lowHead; lowHead = newNode; } else { if(highHead == NULL) newNode->next = NULL; else newNode->next = highHead; highHead = newNode; } } subList = lowHead; return highHead; } /************************************** Main ***************************************/ void print(int &data) { cout << "[" << data << "], "; } int main() { /*Node *n1 = new Node(); n1->data = 5; cout << n1; cout << endl << n1->data; cout << endl << n1->next;*/ srand(time(0)); SortableList l1; for(int i = 0; i < 200; i++) { l1.insert(0, rand()%1000); } /* l1.clear(); l1.insert(0, 10); int data; l1.retrieve(0,data);*/ cout << "Unsorted List: \n"; l1.traverse(print); cout << "\n\n\n\n\n"; l1.quickSort(); cout << "Sorted List: \n"; l1.traverse(print); return 0; }

Linked Quicksort