December 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 4

Total Marks: 15 Marks

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

Click to access
SUGGESTED SOLUTIONS
for Question 4

Briefly describe the selection Sort algorithm.

[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?

[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 ]

[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);

[8]