How does a linear search work?

It checks each item in turn from the start. It carries on until the item is found or the list ends.

A linear search looks for a name that is the fourth item in a list of ten. How many items are checked?

4. The first, second, third and fourth.

items that are next to each other. Neighbours are swapped if they are in the wrong order.

at the end. It "bubbles" along to the end.

A whole pass is made with no swaps. No swaps means no pair is out of order.

3, 6, 5, 8. 6 and 3 swap. 6 and 8 stay. 8 and 5 swap.

In plain words

Two jobs come up constantly with lists: finding an item, and putting the items in order. The syllabus asks for the simplest method of each.

A linear search checks each item in turn, starting from the first, until the item is found or the end of the list is reached.
A linear search works on any list, sorted or not. It can be slow for a long list, because every item may have to be checked.
A bubble sort compares each pair of items that are next to each other, and swaps them if they are in the wrong order.
One trip through the whole list is called a pass. After the first pass, the largest item has moved to the end.
Passes are repeated until one goes right through with no swaps. The list is then in order.

Sort the list 5, 2, 8, 1 into ascending order using a bubble sort.

Pass 1: 5 and 2 swap, giving 2, 5, 8, 1. 5 and 8 stay. 8 and 1 swap, giving 2, 5, 1, 8.
Pass 2: 2 and 5 stay. 5 and 1 swap, giving 2, 1, 5, 8. 5 and 8 stay.
Pass 3: 2 and 1 swap, giving 1, 2, 5, 8. The rest stay.
Pass 4: no swaps are made, so the list is sorted: 1, 2, 5, 8.

A bubble sort only ever compares neighbours. Show the list after each swap, not only at the end.
The sort has not finished until a pass makes no swaps. That last, empty pass is how the algorithm knows it is done.

6 questions, about 2 minutes.

It lands in your notebook with its questions as flashcards.

These are the quiz’s questions. Do the quiz first, then come back here for the ones that got you.

6 questions

Tap an answer and you’ll see straight away whether it’s right, and why.

2 questions, 5 marks. Write your answers on paper, then check them.

Cambridge IGCSE Computer Science 0478 · 5 marks · papermunch.org

Name ______________________________ Date ______________

Describe how a linear search finds an item in a list.[2]
Show answerHide answer
It compares the item with each element of the list in turn, starting with the first. It stops when the item is found or the end of the list is reached.
I got this one
Show the list 4, 9, 2, 7 after the first pass of a bubble sort into ascending order.[3]
Show answerHide answer
4, 2, 7, 9. (4 and 9 stay. 9 and 2 swap. 9 and 7 swap.)
I got this one

1. It compares the item with each element of the list in turn, starting with the first. It stops when the item is found or the end of the list is reached.
2. 4, 2, 7, 9. (4 and 9 stay. 9 and 2 swap. 9 and 7 swap.)