Ch Algo R2

Paper 2 - CT, algorithms programmming

​Last time: programming constructs

Now: CT and arrays revision

Open Ended

What is an array?

Array:

A data structure that holds similar, related data

data = ​[100, 110, 85, 80, 92, 72, 66, 98, 100, 120]

Open Ended

write the code for an array that contains three colours that you like.

Indexing

Items are counted from the left starting at 0

subjects = ["English", "French", "Maths", "Computer Science", "Science"]

Fill in the Blank

subjects = ["English", "French", "Maths", "Computer Science", "Science"], write an expression to print French.

(

[

]

)

2D array

1D array: line of daya

2D array: table

Indexing

Now you have 2 indexes (indices):
Row, Column ..... or ..... Column, Row

Indexing - Col, Row

OCR reference language: table[3, 0]
Python: table[3][0]

Indexing - Row, Col

OCR reference language: table[0, 3]
Python: table[0][3]

Fill in the Blank

The 2D array in the image is stored in the variable numbers. Assuming that it is row,col indexed, write the Python expression that will print out 67

(

[

]

[

]

)

Fill in the Blank

The 2D array in the image is stored in the variable numbers. Assuming that it is row,col indexed, write the OCR reference expression that will print out 67

(

[

,

]

)

Algorithms on data structures

Keywords:

algorithm
abstraction
decomposition

Algorithms on data structures

​Linear Search
Binary Search

Bubble Sort
Merge Sort
Insertion Sort

Linear Search

found = False
for each item in the list:
if item == target:
found = True

Binary Search

Check middle item
if equal, then STOP
if target < middle, repeat on left sub-list
if target > middle, repeat on right sub-list

Bubble sort

for each pass:
for each item from left to right,
compare item with neighbour and swap if out of order

Merge sort

Split into halves (repeatedly) until left with single items
merge pairs of sublists repeatedly (1s, 2s, 4s, 8s, etc.)

Insertion sort

for each item from index 1 to the end:
shift the item left until it reaches a number that is less than it

Interactive

https://gdenes.com/media/games/index.html?gameid=sortsearch