Linear search and bubble sort
Find one value, then order the list
- Syllabus topic 10.2 asks for two algorithms on an array: a linear search and a bubble sort.
- A linear search looks at the cells one by one, from the first. It works on any array, sorted or not.
- Searching does not move the values. Sorting does.
A search can stop early
- A
BOOLEANflag,Found, startsFALSEand becomesTRUEat the first match. - The
WHILEtest checks two things: not found yet, and still inside the array. So a missing value never reads past the last cell. - After the loop,
Foundsays whether it was there, andIndexsays where.
DECLARE Names : ARRAY[1:5] OF STRING
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
Names[1] ← "Ada"
Names[2] ← "Bo"
Names[3] ← "Cy"
Names[4] ← "Di"
Names[5] ← "Ed"
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 5
IF Names[Index] = "Di" THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Di is at index ", Index
ELSE
OUTPUT "Di is not in the list"
ENDIF
- A
FORloop over every cell works too: set a position variable to0first, and storeIndexwhen a cell matches. That form always looks at all the cells.
Bubble the largest to the end
- Compare each pair of neighbours. When the left one is larger, swap them through a temporary variable.
- After pass 1 the largest value is in the last cell. After pass 2 the two largest are in place, and so on.
nvalues need at mostn - 1passes, and each pass comparesn - 1pairs.
A swap needs three steps
| Step | A[J] |
A[J + 1] |
Temp |
|---|---|---|---|
| start | 8 | 3 | – |
Temp ← A[J] |
8 | 3 | 8 |
A[J] ← A[J + 1] |
3 | 3 | 8 |
A[J + 1] ← Temp |
3 | 8 | 8 |
- Without
Temp, the second line would overwrite the 8 before it is saved, and both cells would hold 3.
DECLARE Heights : ARRAY[1:5] OF INTEGER
DECLARE Pass, J, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Heights[1] ← 160
Heights[2] ← 152
Heights[3] ← 171
Heights[4] ← 148
Heights[5] ← 165
Pass ← 1
REPEAT
Swapped ← FALSE
FOR J ← 1 TO 4
IF Heights[J] > Heights[J + 1] THEN
Temp ← Heights[J]
Heights[J] ← Heights[J + 1]
Heights[J + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT J
OUTPUT "After pass ", Pass, ": ", Heights[1], " ", Heights[2], " ", Heights[3], " ", Heights[4], " ", Heights[5]
Pass ← Pass + 1
UNTIL Swapped = FALSE
| After pass | Array | Swaps in the pass |
|---|---|---|
| 1 | 152 160 148 165 171 | yes: 171 has reached the end |
| 2 | 152 148 160 165 171 | yes |
| 3 | 148 152 160 165 171 | yes |
| 4 | 148 152 160 165 171 | none, so the sort stops |
- The
Swappedflag stops the sort as soon as a pass changes nothing. A fixed number of passes (aFORloop ofn - 1passes) gives the same result.
Common mistakes
| Wrong | Right | Why |
|---|---|---|
Score[J] ← Score[J + 1] alone |
the three-step swap through Temp |
the left value is lost |
FOR J ← 1 TO 4 with 4 values |
FOR J ← 1 TO 3 |
Score[J + 1] would read cell 5, outside the array |
one FOR J loop only |
an outer loop of passes around it | one pass moves only the largest value into place |
WHILE Names[Index] <> "Di" |
also test Index <= 5 |
a missing value would read past the end |
the inner NEXT names I |
NEXT J inside, NEXT I outside |
each NEXT closes its own loop |
Now you try
- The tasks use their own arrays. For the search, report where
9sits. For the sort, four values need three pairs per pass.
Independent transfer
The final task has no supplied algorithm. Plan its inputs, processing and outputs, then solve it before opening support. Check more than the sample case.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
The array Values يحتفظ بـ 4, 9, 1, 7. Set Pos to the index of 9 (it is 2) and output Pos. If you never find it, Pos stays 0.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
The array Score يحتفظ بـ 4, 1, 3, 2. Bubble-sort it into ascending order and output the four values, one per line.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Read NumberOfValues (1 to 6), NumberOfValues integers, then Target. Output the LAST matching index, or 0 if absent.
اضغط تشغيل لرؤية المخرجات هنا.