Searching and Sorting Algorithms

Searching and sorting are two of the most common operations in computing, and the IB course expects you to describe, trace, and compare the standard algorithms. The three you must know well are linear search, binary search, and bubble sort.

Linear search

Linear search (also called sequential search) checks each element of a collection one at a time, from the first to the last, until it finds the target value or reaches the end. It makes no assumptions about the data, so it works on both sorted and unsorted lists.

FOUND = false
loop INDEX from 0 to SIZE - 1
    if DATA[INDEX] = TARGET then
        FOUND = true
        POSITION = INDEX
    end if
end loop
if FOUND = true then
    output "Found at ", POSITION
else
    output "Not found"
end if

In the worst case, the target is last or absent,