PROBLEM $3$: $(25$ points$)$

In this problem you will write all or part of two functions that sort an unsorted linked list into

descending order. You will write all of one function, InsertionListDescendinglter. This function uses the

insertion sort algorithm to sort the input linked list into a new linked list. You will also write two helper

functions to implement the selection sort algorithm SelectionListDescendingRec. The selection sort will

modify the input list. The prototype of these two sorting functions will be$,$

LinkedList $*$ InsertionListDescendingIter$($const LinkedList $*$ head$)$;

void SelectionListDescendingRec$($const LinkedList $*$ head$)$;

To help you complete these tasks you will be supplied with a file containing the following framework:

the definitions of the LinkedList and LinkNode structures.

the implementations of two functions which you may use in your insertion sort function.

void insertListNode$($LinkedList$*$ list, double val$)$;

LinkedList $*$ createLinkedList$()$;

the implementation of function SelectionListDescendingRec.

the implementation of other LinkedList functions that may be used in testing of your functions.

These functions may not be used within the functions you write.

Two initial tests, using the functions described in the previous point that should produce the

following output. You will need to do additional testing yourself to make sure your code

functions for all possible cases.

Original linked list:

$88\mathrm{.}00000023\mathrm{.}00000036\mathrm{.}00000017\mathrm{.}0000002\mathrm{.}00000063\mathrm{.}00000028\mathrm{.}000000$

Insertion sort sorted linked list:

$88\mathrm{.}00000063\mathrm{.}00000036\mathrm{.}00000028\mathrm{.}00000023\mathrm{.}00000017\mathrm{.}0000002\mathrm{.}000000$

Original List

$88\mathrm{.}00000083\mathrm{.}00000045\mathrm{.}00000027\mathrm{.}00000091\mathrm{.}00000076\mathrm{.}00000062\mathrm{.}000000$

Selection sort sorted List

$91\mathrm{.}00000088\mathrm{.}00000083\mathrm{.}00000076\mathrm{.}00000062\mathrm{.}00000045\mathrm{.}00000027\mathrm{.}000000$

The functions you will write are:

A$.$ Two helper functions called by the selection sort function, SelectionListDescendingRec:

void swapValues$($ListNode$*$ node$1,$ ListNode$*$ node$2)$;

Function, swapValues, takes pointers to two ListNodes as its arguments. The function

exchanges the values in the two ListNodes pointed to by the two pointers.

ListNode $*$ findMax$($ListNode$*$ start, ListNode$*$ maxNode$)$;

Function findMax

recursively finds the pointer to the ListNode with the largest value.

The pointer to the ListNode containing the largest pointer is returned as return value of

the value of the function.

Begins looking for the ListNode with the largest value at the ListNode pointed to by

pointer start. The ListNode pointed to by the pointer start can be any ListNode in the

linked list.

B$.$ LinkedList $*$ InsertionListDescendinglter$($const LinkedList$*$ head$)$;

Consider the function, InsertionListDescendinglter, for insertion sort.

The pointer to the original unsorted linked list is passed into the function. The list pointed to by

this pointer will not be changed in any way by your insertion sort function.

Your insertion sort function will create a new sorted linked list containing links holding the same

values as the original list.

All new links will be allocated dynamically.

The pointer to the new list will be passed back to the calling function as its return value.

The solution inside your insertion sort function may call only the supplied functions listed below:

void insertListNode$($LinkedList$*$ list, double val$)$;

LinkedList$*$ createLinkedList$()$;

To implement the insertion sort, repeat the next $3$ steps until all nodes have been inserted into the new

list:

Select the next link in the linked list.

Make a new link containing the value in the selected link.

Insert the new link into the new list.

Stop when the next pointer in the current node is NULL.

Please note the following constraints for all three functions:

You may not use global variables.

Your code must not contain memory leaks or dangling pointers.

$**$THIS CODE SHOULD BE WRITTEN IN C$**$