2.1.3 Revision Test

​ (a)   search works by starting at the beginning of a list and checking if that item is the one being searched for. It then looks at the ​ (b)   one and continues until either it finds the item searched for or reaches the ​ (c)   of the list. If it reaches the end of the list, then the item was not in the list.

• Linear
• next
• end

A ​ (a)   search will only work on a ​ (b)   list. It works by finding the ​ (c)   item and comparing it to the searched item. If it is the item, it returns that it is found. If it is ​ (d)   than the searched for item, then the top half of the list is discarded. If it is less, the ​ (e)   half is discarded. The process is repeated on the remainder of the list until the item is found or you end up with a list of one, which is not the item. Then we know it is not in the list.

• binary
• sorted
• middle
• greater
• bottom

​ (a)   sort works by starting at the first item and comparing it to the next. If they are out of order it ​ (b)   them. It continues through the list swapping items when they are out of order till it reaches the end. It then ​ (c)   the entire process until a full pass is completed with ​ (d)   swaps. When the swaps are made, it does a three-way swap using a ​ (e)   variable to hold the data during the swap.

• Bubble
• swaps
• repeats
• no
• temporary

An ​ (a)   sort works by starting with a sublist of ​ (b)   item at the start of the list. A list of one is naturally ​ (c)   . Starting with the next item, the items are compared with the one ​ (d)   to it and if out of place swapped. This continues until either it does not need to be swapped or is at the ​ (e)   of the list, at which point it is also sorted. Once all the items are inserted the entire list is sorted.

• insertion
• one
• sorted
• prior
• bottom

A merge sort uses a ​ (a)   and ​ (b)   algorithm and works by ​ (c)   the list in half. Each sublist is further split in half until all items are in lists of ​ (d)   . The algorithm then works by ​ (e)   the split lists, but it does it by taking items from the now sorted lists in order and recombining them in order.

• conquer
• divide
• splitting
• one
• recombining