4.2 Thinking in Program Design Flashcards
What are the four standard algorithms?
Sequential Search
Binary Search
Bubble Sort
Selection Sort
What is Sequential Search?
Start at the start of an unsorted list comparing items until you find what you want.
What is a Binary Search?
Start at centre of sorted array, comparing with values and going lower or higher.
What is Bubble Sort?
Comparing adjacent tiles and switching them if they are in the wrong order.
What is Selection Sort?
Divides list into two parts, sorted and un sorted. Finds the smallest and puts it at the beginning.
Evaluate Binary Search
Faster O(log n) but can only be a sorted list.
Evaluate Sequential Search
Slower O(n)
but can be performed on an unsorted list
Evaluate Bubble Sort
Can quit early if few swaps are needed but on bigger code will need lots of swaps.
Evaluation Selection Sort
Must always perform n swaps, it can’t finish early.
But is better on longer lists
What is this?
Terminator - start or end value.
What is this?
Input/Output
What is this?
Process - something is happening.
What is this?
Decision.
What is used to measure the efficiency of an algorithm?
Run Time,
What can affect the run time of an algorithm?
Computer/Hardware
Representation of ADTs
Efficiency of Compiler
Competence of Programmer
Complexity of Algorithm
Size of Input
