Search And Sort

Question 1

Linear search

Answer 1

. Start with first item in list
. Each item is compared to the wanted item
. This is fine in order
. The search stops if item is found or end of list
. Doesn’t have to be ordered

Question 2

Binary search

Answer 2

. Must be in order
. Midpoint of list is found
. Compare midpoint to the searched item
. If matches, item found
. If not, check if greater than or less than
. If greater than, cross out all elements left of the midpoint and find new midpoint
. Check again and repeat until item found or one item left

Question 3

Bubble sort

Answer 3

. Items are compared in pairs
. Starts with first and second item
. If in wrong order, swap
. Moves to second and third
. Repeats until end of list is reached
. If any swaps made during this time, do it again until no swaps

Question 4

Merge sort

Answer 4

. List is split into two sub lists.
. Continues to split until every item is along
. Items are merged and sorted in one step.
. First item in the first two sub list are compared
. Continue to merge until there is just one sorted list

Question 5

Insertion sort

Answer 5

. Start with first item in list
. Goes along, putting each item in correct place
. Does a final run through to check they’re all correct
. Once no swaps made, list is sorted