Algorithms

Binary Search

Binary Search

Starting at the middle item of the list and repeatedly dividing the list in half

Linear Search

Going through all the items in a list until the target item is found

Binary search pseudocode

found = false

first = 0

last = items.length - 1

while first <= last and Found == false

midpoint = (first + last) DIV 2

if items [midpoint] == item_to_find then

found = true

else

if items [midpoint] = item_to_find then

first = midpoint + 1

else

last = midpoint - 1

end if

end if

end while

Bubble sort

Continuously goes through a list until the list has been sorted.

• It looks at the current value and checks it with the adjacent value. If the adjacent value is higher, the numbers are swapped

• Each swap is called a pass

Bubble sort pseudocode

numbers = [9, 5, 4, 15, 3, 8, 11]

numItems = len(numbers

while i < (numItems - 1) and (flag=true)

flag = false

for j = 0 to (numItems - i - 2)

if number [j] > numbers [j+1]

temp = numbers [j]

numbers [j] = numbers [j+1]

numbers [j+1] = temp

flag = true

end if

print (numbers)

next i

Linear Search pseudocode

choice = input

found = false

counter = 0

while counter < len (names) and Found = false

if array [counter] = choice:

Found = true

position = counter

end if

counter = counter + 1

end while

Insertion Sort

Sorting into two columns, sorted & unsorted

• The items from the unsorted column are moved to the sorted column in every pass

Insertion Sort pseudocode

First = 0

last = MaxItems

for count2 = First + 1 to last

currentItem = list(count2)

count = count2 - 1

do while list(count) > currentItem and count2 > 0

list (count+1) = list (count)

count = count - 1

loop

list(count + 1 = currentItem)

Next