1 Given the following list of keys (3, 18, 29, 32, 39, 44, 67, 75), show the contents of the array after each iteration of the outer loop for the
(a) bubble sort (b) selection sort (c) insertion sort
2 Evaluate the insertion sort algorithm to determine the best case and the worst case time complexities.
3 Implement the following functions related to the singly linked list:
(a) The removeAll(head) function, which accepts a head reference to a singly linked list, unlinks and remove every node individually from the list.
(b) The splitInHalf(head) function, which accepts a head reference to a singly linked list, splits the list in half and returns the head reference to the head node of the second half of the list. If the original list contains a single node, None should be returned.