COMPUTER SCIENCE 9618
PSEUDO-CODE - Bubble Sort (Answers)
9618/21/M/J/25/Q6(b)
(b) Each sensor used in the system has a unique sensor ID number in the range 1 to 50.
The program that is used to monitor the speed of each vehicle reads each sensor value every second and stores this value along with the sensor’s unique ID into a global 2D array Reading.
The global array Reading has been declared as follows:
DECLARE Reading : ARRAY[1:2000, 1:2] OF INTEGER.
The array contains 4000 elements organised as 2000 rows and 2 columns.
Column 1 contains the sensor value, and column 2 contains the sensor ID.
When 2000 sensor readings have been taken, the array is full and the system stops taking any more sensor readings until the array has been processed.
A procedure Sort() is needed to sort the array into ascending order of sensor value using an efficient bubble sort algorithm.
Write efficient pseudocode for the procedure Sort() [8]
Steps:
PROCEDURE Sort()
DECLARE Temp, J, Boundary : INTEGER
DECLARE NoSwaps : BOOLEAN
Boundary ← 1999
REPEAT
NoSwaps ← TRUE
FOR J ← 1 TO Boundary
IF Reading[J,1] > Reading[J+1,1] THEN // Swap sensor values
Temp ← Reading[J,1]
Reading[J,1] ← Reading[J+1,1]
Reading[J+1,1] ← Temp
Temp ← Reading[J,2] // Swap sensor IDs
Reading[J,2] ← Reading[J+1,2]
Reading[J+1,2] ← Temp
NoSwaps ← FALSE
ENDIF
NEXT J
Boundary ← Boundary - 1
UNTIL NoSwaps = TRUE
ENDPROCEDURE
9618/21/M/J/23/Q8(b)
(b) A new module has been defined:
Write efficient pseudocode for module CheckNewItem(). [7]
FUNCTION CheckNewItem(NewLine : STRING) RETURNS BOOLEAN
DECLARE NotFound : BOOLEAN
DECLARE NewItemNum, ThisItemNum, ThisLine : STRING
NotFound <- TRUE
ThisItemNum <- "0000"
OPENFILE "Stock.txt" FOR READ
NewItemNum <- LEFT(NewLine, 4)
WHILE NOT EOF("Stock.txt") AND NotFound = TRUE AND ThisItemNum < NewItemNum
READFILE("Stock.txt", ThisLine)
ThisItemNum <- LEFT(ThisLine, 4)
IF ThisItemNum = NewItemNum THEN
NotFound <- FALSE
ENDIF
ENDWHILE
CLOSEFILE "Stock.txt"
RETURN NotFound
END FUNCTION
9618/22/O/N/22/Q7(b)
(b) Write an efficient bubble sort algorithm in pseudocode for module SortArrays().
Steps:
9618/23/O/N/22/Q7(b.i)
(b) (i) Two additional modules are defined:
Write pseudocode for the module AddError(). Assume that the error code is not already in the ErrCode array.
9618/21/M/J/21/Q5
Q5) A global 2D array Result of type INTEGER is used to store a list of exam candidate numbers together with their marks. The array contains 2000 elements, organised as 1000 rows and 2 columns.
Column 1 contains the candidate number and column 2 contains the mark for the corresponding candidate. All elements contain valid exam result data.
A procedure Sort() is needed to sort Result into ascending order of mark using an efficient bubble sort algorithm.
Write pseudocode for the procedure Sort(). [8]
Steps:
9618/21/O/N/21/Q2(a)
Q2a) An algorithm to sort a 1D array into ascending order is described as follows:
• move the largest value to the end
• keep repeating until the array is sorted.
Apply the process of stepwise refinement to this algorithm in order to produce a more detailed description.
Write the more detailed description using structured English. Your explanation of the algorithm should not include pseudocode statements. [6]
0 Reviews