Searches and Sorts

Question 1

What is the pseudocode for the binary search?

Answer 1

found = False
first = 0
last = items.Length - 1 

while (first <= last and found == false)
          midpoint = (first + last) DIV 2
          if (items[midpoint] == itemToFind then
                    found = True
          else
                    if (items[midpoint] < itemToFind then
                              first = midpoint + 1
                    else
                               last = midpoint - 1

Question 2

What is the pseudocode for the linear search?

Answer 2

found = False
index = 0

while (found == false and index < items.Length)
          if (items[index] == itemToFind
                    found = true
          else
                    index = index + 1

Question 3

What is the pseudocode for the bubble sort?

Answer 3

n = items.Length
swapped = true

while (n > 0 and swapped == true)
swapped = false
n = n - 1
for (index = 0 TO n - 1)
if (items[index] > items[index+1]
Swap(items[index], items[index+1])
swapped = true

Question 4

What is the pseudocode for the insertion sort?

Answer 4

for (i = 1 TO items.Length)
current = items[i]
j = i

      while (j > 0 AND items[j - 1] > current
                items[j] = items[j - 1]
                j = j - 1
      end while
      items[j] = current end for