December 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 4

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 3
• Question 5
• Cover Page

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 4

Briefly describe the selection Sort algorithm.

Selection sort:

•Moves the first item in the list that has not been sorted to the first unsorted position;(1 mark)

•By swapping the two values around;(1 mark)

[2]

When a list of size N is sorted by selection sort, how many passes of the list are required to ensure the list is sorted?

N -1 passes of the list are required.

[1]

Given the unsorted list x below,show the state of the list after each pass of a descending selection sort.

x =[2 ,6 ,13 ,7 ,12 ]

•x =[2 ,6 ,13 ,7 ,12 ]

•x =[13 ,6 ,2 ,7 ,12 ](1 mark)

•x =[13 ,12 ,2 ,7 ,6 ](1 mark)

•x =[13 ,12 ,7 ,2 ,6 ](1 mark)

•x =[13 ,12 ,7 ,6 ,2 ](1 mark)

[4]

Assume the following definition of a dynamic linked list:

TYPE
       NodePtr = ˆNode;

       Node     = RECORD
                              Datum :INTEGER;
                              Forward,Back :NodePtr;
                      END;

       List       = RECORD
                              Front,Rear :NodePtr;
                      END;

FUNCTION Length(x : List) : INTEGER;
                 {Returns the length of the list x.}

FUNCTION ValAt(x : NodePtr) : INTEGER;
                 {Returns the value stored at the node x.}

FUNCTION ResetIterator(x : List) : NodePtr;
                 {Returns a pointer to the start of the list x.}

PROCEDURE MoveIteratorAlong(VAR x : NodePtr);;
                     {Moves the pointer x one node along the list.}

PROCEDURE Swap(VAR x : NodePtr, VAR y : NodePtr);
                      {Swaps the values stored at the nodes x and y.}

Write a procedure DescendingSelectionSort , the signature of which is given below, which takes an unsorted list of the type given above and performs a descending selection sort on the list.You may assume the existence of the procedures and functions whose signatures are given above.

PROCEDURE DescendingSelectionSort(VAR x :List);

A sample definition of DescendingSelectionSort follows:

PROCEDURE DescendingSelectionSort(VAR x : List);
VAR a, b, indicator : NodePtr;
VAR greatest : INTEGER;
BEGIN
       a:= ResetIterator(x);
       FOR i= 0 TO (Length(x)-1) DO
       BEGIN
             greatest:= ValAt(a);
             indicator:= a;
             b:= a;
             FOR j= i+1 TO Length(x)DO
             BEGIN
                   MoveIteratorAlong(b);
                   IF(ValAt(b) > greatest ) THEN
                   BEGIN
                          indicator:= b;
                          greatest:= ValAt(b);
                   END;
                   Swap(a, indicator);
             END;
             MoveIteratorAlong(a);
       END;
END;{ DescendingSelectionSort }

And the following marking scheme should be used:

•Declaring an iterator a ,and setting it to the start of the list using
ResetIterator ;(1 mark)

•Declaring an outer loop,bounded from 0 to Length(x)-1 ;(1 mark)

•Declaring a greatest counter,and initialising it with ValAt(a);(1 mark)

•Declaring the iterators b and indicator ,and initialising them to a on each iteration of the outer loop;(1 mark)

•Declaring an inner loop,bounded from i+1 to Length(x);(1 mark)

•Incrementing the b iterator on each iteration of the inner loop,using MoveIteratorAlong ;(1 mark)

•Comparing the current value and the greatest value,and updating indicator and greatest if the current value is greater;(1 mark)

•Swapping a and the indicator iterator before the inner loop completes an iteration.(1 mark)

[8]