Dec 1998 AP207: Advanced Programming Techniques (Question 5)

	The question is concerned with the implementation of a descending sort procedure that uses the insertion sort algorithm. For example, sorting the sequence [7, 3, 2, 1, 9] produces [9, 7, 3, 2, 1]. The definition of a linked list type, a prototype for the procedure Insert and the procedure InsertSort are given below. TYPE List = ^Node; Node = RECORD Item : Integer; Next : List END; PROCEDURE Insert(x: List; VAR xs: List); PROCEDURE InsertionSort(VAR xs: List); VAR rest, singleton, result: List; BEGIN rest := xs; result := Nil; WHILE (rest <> Nil) DO BEGIN singleton := rest; rest := rest^.Next; singleton^.Next := Nil; Insert(singleton, result); END xs := result END; The procedure insert (to be defined later) takes a singleton list x and a sorted list xs as its arguments, and inserts the element stored in the singleton list into a sorted list such that the list xs remains in descending sorted order. For example, the figure below shows an example list before and after adding the singleton element 3:
(a)	Informally describe the insertion sorting algorithm used in the Pascal procedure InsertionSort above.	[3]
	Three marks for an adequate description of the algorithm. Award the marks as follows: one mark for identifying that a temporary list that will contain all the sorted elements is built incrementally from a new list. one mark for identifying that N insertions will occur (where N is the length of the list to be sorted). Alternatively, the students may say that every element in the list to be sorted is traversed, and inserted into the temporary list. one mark for saying that insert is used to place each element in the temporary sorted list
(b)	Give the list [2, 5, 1, 4], draw four diagrams that show the states of the lists rest and result immediately after each execution of insert.	[8]
	Two marks for each correct diagram showing rest and result in the four stages below:
(c)	How many list elements would have to be traversed by all the invocations of the insert procedure given:
	(i) an already sorted list of size N passed to InsertionSort? i.e., what is the worst case cost, or upper-bound complexiy of insertion sort?	[1]
	N², or, O(N²)
	(ii) a list in descending order of values of size N passed to InsertionSort? i.e., what is the best case cost, or lower-bound complexity of insertion sort?	[1]
	N, or, O(N)
(d)	Define the procedure Insert.	[7]
	PROCEDURE Insert(x: List; VAR xs: List); VAR temp, drag: List; BEGIN IF (xs = Nil) THEN xs:=x; ELSE IF (xs^.Item < x^.Item) THEN BEGIN x^.Next := xs; xs := x END ELSE BEGIN temp:=xs; drag:=Nil; WHILE ((temp <> Nil) AND (x^.Item < temp^.Item) DO BEGIN drag:=temp; temp:=temp^.Next END; x^.Next := temp; drag^.Next := x; END END; one mark for updating xs with x if xs is empty. two marks for inserting x onto the front of the list if it is larger than the first element in the list. two marks for iterating down the list to find the right position to insert the element x. one mark for ensuring that there are no problems if x is the largest element in the sequence (i.e., check to see if temp is Nil, so that temp is not dereferenced). one mark for patching up the next field of x to point to the correct element in the sequence. No marks should be deducted for trivial syntactic errors.