write a c++ code 6. Implement quicksort for linked lists. You are required to im

Question

write a c++ code 6. Implement quicksort for linked lists. You are required to implement the linked quicksort

template class Sortable_list:public List {

public: void quick_sort(); protected: // Add prototypes for auxiliary functions here };

template void Sortable_list::quick_sort() /* Post: The entries of the Sortable_list have been rearranged so that the keys in all the entries are sorted into nondecreasing order. */ { }

In linked quicksort, use the first entry of a sublist as the pivot for partitioning. The partitioning function for linked lists is relatively easier than that for contiguous lists, since minimization of data movement is not a concern. To partition a sublist, you only need to traverse it, removing each entry from the list as you go, and then add the entry to one of two lists depending on the key value relative to the pivot. However, since partition now produces two new lists, you will need to combine the two sorted sublists along with the pivot into a single linked list in your recursive_quick_sort() helper function.

Explanation / Answer

struct Node *partition(struct Node *head, struct Node *end,
struct Node **nh, struct Node **ne)
{
struct Node *pi = end;
struct Node *pr = NULL, *cu = head, *ta = pi;

while (cu != pi)
{
if (cu->data < pi->data)
{
  
if ((*nh) == NULL)
(*nh) = cu;

pr = cu;
cu = cu->next;
}
else
{
  
if (pr)
pr->next = cu->next;
struct Node *tm = cu->next;
cu->next = NULL;
ta->next = cu;
ta = cu;
cu = tm;
}
}

if ((*nh) == NULL)
(*nh) = pi;

(*ne) = ta;
return pi;
}


struct Node *quick(struct Node *head, struct Node *end)
{
  
if (!head || head == end)
return head;

Node *nh = NULL, *ne = NULL;

struct Node *pi = partition(head, end, &nh, &ne);

if (nh != pi)
{
struct Node *tm = nh;
while (tm->next != pi)
tm = tm->next;
tm->next = NULL;

  
nh = quick(nh, tm);

  
tm = Tail(nh);
tm->next = pi;
}

pi->next = quick(pi->next, ne);

return nh;
}

void quickSort(struct Node **hed)
{
(*hed) = quick(*hed, Tail(*hed));
return;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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