2.3.1 Algorithms

Pros • Okay for smaller data sets Cons • Inefficient for larger data sets. • Very inefficient for reversing the order of a data set. • The most inefficient algorithm of the sorts studied in the course.

Allows you to swap two values without overwriting one of them.

When the algorithm reaches the end of a pass, if the Boolean is true then the list may not be sorted, so it needs to make at least one more pass. If the end of the pass is reached and it is false, then then you have gone through the list, made no changes, so the list is sorted.

• Compares each pair of data • If they are in the correct order it moves to the next pair • If they are in the wrong order it swaps them • Continues to the end of the array • If there has been a swap it checks again • If there have been no swaps then it is sorted

• Splits the list into sorted and unsorted • The first item in the list is classed as sorted • Insert one number at a time from the unsorted list into correct position by moving backwards through the list of sorted numbers

Pros * Simplest Sort to code * One of the fastest algorithms for sorting very small arrays Cons * Impractical for sorting large arrays.

• Start at the first element, if equal to search item, then report found • If not equal, then move to next element (incrementally) • Repeat for all elements until found or the end of the list reached

Pros * Can work on both ordered and unordered data sets * Can have multiple processors searching different areas at the same time. * Scales very with additional processors Cons * If the item is not in the list, then all items will be searched, this makes is a slow algorithm for large lists.

• Find mid-point, if equal to mid-point then report found • If less than mid-point then make sub-list from left • If greater than mid-point then make sub-list from right • Repeat with sub-list until found or sub-list is empty

• Calculate array midpoint by adding the array lower bound to the array upper bound, using the DIV command divide it by 2 (equivalent to rounding down) • Compare array midpoint with value to search for, if equal set found flag to true • if array midpoint < value to search for, change lowerbound to equal midpoint + 1 • if array midpoint > value to search for, change upperbound to equal midpoint – 1 • Repeat until lowerbound is greater than or equal to upperbound

• Find the mid-point in the list: 21 (index 3) • Compare it to the value 47, match = false • 47 is greater than middle point, so new subset is 46-51 • Find the middle of the new subset (47 index 5) • Is this value equal to 47, true Search finishes

Pros * Halves the list each time so works well on large data sets * Efficient as does not need to search every single element/uses divide and conquer Cons * Only works on an ordered set of data

lines 7 and 8 could swap around depending on how the stack pointer is used

• Dynamic Data Structure • Enqueue • Dequeue • First in First Out • Peek • Front Pointer • Rear Pointer • Circular / Non-Circular

• Dynamic Data Structure • Pop • Push • First in Last Out (LIFO) • Peek • Top Pointer

lines 7 and 8 could swap around depending on how the stack pointer is used