Course 7.3Lesson 2 of 3
A linear search looks through a list item by item until it finds what it wants. A bubble sort puts a list in order by comparing neighbours and swapping them. You write both in pseudocode, dry-run them, and count their comparisons and passes.
Try the code and the simulations beside the lesson.
How do you find a friend's name on an unsorted class list? You start at the top and read each name until you find it, or reach the end. That is a linear search.
The lists in this lesson are arrays: a set of values under one name, each at a numbered position called an index. Names[3] is the value at index . Arrays are taught fully in the next chapter. Here we only read and swap their values.
The array Names holds Ravi, Lena, Omar, Mei, Tariq and Zoe, at the indexes to .
DECLARE Names : ARRAY[1:6] OF STRING
INPUT Wanted
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 6 DO
IF Names[Index] = Wanted
THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT Wanted, " found at position ", Index
ELSE
OUTPUT Wanted, " not found"
ENDIFThe loop stops for one of two reasons: the name is found, or every index has been checked. The flag Found records which. Searching for Mei takes comparisons. Searching for a name that is not there takes all .
A linear search works on any list, sorted or not. Its weakness is speed: a long list may need a comparison for every item. The Python Essentials chapter "Searching and Sorting" also shows a faster search for sorted lists, which this syllabus does not ask for.
A bubble sort puts values in order by comparing neighbours. If a pair is in the wrong order, it is swapped. One sweep from the start to the end is a pass. After the first pass, the largest value has "bubbled" to the end. Each pass puts one more value in its final place.
DECLARE Scores : ARRAY[1:5] OF INTEGER
Last ← 5
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO Last - 1
IF Scores[Index] > Scores[Index + 1]
THEN
Temp ← Scores[Index]
Scores[Index] ← Scores[Index + 1]
Scores[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Last ← Last - 1
UNTIL Swapped = FALSE OR Last = 1Three lines swap a pair, with Temp holding one value for a moment. Without Temp, one value would be lost. The flag Swapped stops the sort early: a pass with no swaps means the list is already in order. Last shortens each pass, because the end of the list is already sorted.
The picture sorts , , , , . Follow pass 1.
After comparisons, is in its final place. Pass 2 needs only comparisons, pass 3 needs , and pass 4 needs . For items a pass makes at most comparisons, and the whole sort makes at most .
To sort into descending order, change only the comparison: IF Scores[Index] < Scores[Index + 1].
The grey blocks marked pseudocode are written in the exam style and do not run. The Python box is the same algorithm in Python, and that one runs. Python can swap two values in one line, a, b = b, a, so it needs no Temp. The pseudocode needs the three-line swap.
A ← B then B ← A leaves both equal to B.Index with Index + 1 only up to Last - 1.Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Every lesson is open to read. Enrolling also lets you:
Log in to join the discussion.
Loading…
This lesson is free to read. Enroll free to keep your place in the course.