Apr 1999 AP207: Advanced Programming Techniques (Question 5)

(a)	(i) Describe informally the bubble sort algorithm.	[2]
	Bubble sort algorithm involves the comparison of 2 adjacent elements and placed them in the required order. Typically, item 1 and 2 will be compared, followed by 2 and 3, and so on.
	(ii) Describe informally the quick sort algorithm.	[2]
	Quick sort algorithm involves sorting a list using pivot point where larger elements are placed on one side while smaller elements are placed on the other side of the pivot point. The results is a sublist. From here, then the above procedure will be repeated (in the sublist).
	(iii) Describe informally the selection sort algorithm.	[2]
	Selection Sort alorigthm (e.g when sorting in ascending order) will compare every elements in the list and the smallest item will then be placed in the left side of list. Upon this, this smallest item will be fixed in this point. Next, the rest of the list (except this smallest item) will go through the above procedure and the next smaller item will be placed on right of the first smallest time. This continues till end of list.
(b)	(i) The procedure BubbleSort takes an unsorted list x and iterates through the list, performing a bubble sort on at most one pair until the list is sorted. Show the state of the following list after each complete iteration of the BubbleSort procedure, assuming that a sorted list is one in which the value of each item increases along the list: 10, 5, 4, 1	[4]
	Bubblesort 1st pass 10,5,4,1 (original list) 5,10,4,1 5,4,10,1 5,4,1,10 2nd pass 5,4,1 4,5,1 4,1,5 3rd pass 4,1 1,4 The resulting list -> 1, 4,5 10
	(ii) The procedure SelectionSort takes an unsorted list x and iterates through the list, performing a selection sort on at most one pair until the list is sorted. Show the state of the following list after each iteration of the SelectionSort procedure, assuming that a sorted list is one in which the value of each item increases along the list: 12, 10, 6, 3, 7, 1	[4]
	Selection list 12, 10, 6 , 3 , 7, 1 (original) After 1st pass, 1,10,6,3,7,12 After 2nd pass 1,3,6,10,7,12 After 3rd pass 1,3,6,10,7,12 After 4th pass 1,3,6,7,10,12 After 5th pass 1,3,6,7,10,12
(c)	Define the procedure Procedure SelectionSort(Var List: ListType; ListSize: Integer) used above, such that the procedure will take an unsorted list of integers and return a list which has been sorted using a selection sort into increasing order.	[6]
	Procedure SelectionSort(Var List : ListType; Var position , i : integer ; ListSize : Integer) temp, small : integer Begin for i:= 1 to ListSize -1 do Begin if small : = List [i]; for j:= i + 1 to ListSize do Begin if small > List [i} then Begin small : = List [j]; position : = j; end ; end ; temp = List [i] List [i] = List [j]; List [j] = temp; end;