Someone please help me answer this i need it ASAP. I will go give you an immedia

Question

Someone please help me answer this i need it ASAP. I will go give you an immediate thumps up

Thanks in advance!

Q7: Sort the list of books in the container (10 points) File: Main.cpp // sortDatabase() // Q7 Use a recursive function, such as quick sort or merge sort, to sort the // container list by the book name in alphabetical order. // You can create a new list. In this case, you must delete the old list(garbage collection) // You may browse books and websites for a suitable implementation of sorting and modify it as per the need of this program. You must cite the book/website that you used.

Explanation / Answer

Please find below the complete method implementation of sortDatabase() and its helper methods.

Since no background is given for the problem statement, it is assumed that we are sorting a single linked list where reference to the head is provided.

//helper method to get the last element
Container getLast(Container *current) {
while (current != NULL) {
current = current.next;
}
return current
}

//helper method to create partition and return pivot
Container partition( Container *head, Container *end, Container **bufferHead, Container **bufferLast) {

Container *pivotElement = end;
Container *previous = NULL;
Container *current = head;
Container *last = pivotElement;

while( current != pivotElement) {
if (current.data < pivotElement.data){
if ( (*bufferHead) == NULL){
(*bufferHead) = current;
}
previous = current ;
current = current.next;
} else {
if (previous) {
previous.next = current.next;
}
Container *buffer = current.next;
current.next = NULL;
last.next = current;
last = current;
current = buffer ;
}
}

if((*bufferHead) ==NULL) {
(*bufferHead) = pivotElement;
}
(*bufferLast) = last;

return pivotElement;
}

//recursive quick sort method
Container quickSortDatabase(Container *head, Container *last) {

if(!head || head == end) {
return head;
}

Container *bufferHead = NULL;
Container *bufferLast = NULL;

Container *pivotElement = findPivot( head, last, &bufferHead, &bufferLast) ;

if(bufferHead != pivotElement) {
Container *buffer = bufferHead;
while ( buffer.next != pivotElement ) {
buffer = buffer.next;
}
buffer.next = NULL;
bufferHead = quickSortDatabase( bufferHead, buffer) ;
buffer = getLast(bufferHead) ;
buffer.next = pivotElement;
}
pivotElement.next = quickSortDatabase( pivotElement.next, bufferEnd) ;
return bufferHead;
}

void sortDatabase(Container **head) {
(*head) = quickSortDatabase(*head, getLast(*head)) ;
return;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.