Topic 6 Flashcards
What is abstraction?
Removing unnecessary details from a problem in order to solve it.
what is decomposition?
Breaking down a problem into smaller more manageable parts.
A linear search requires the data to be in which order?
Unsorted data
A binary search requires the data to be in which order?
Sorted data - i.e numerical or alphabetical
How does a linear search work?
Start at the beginning of a list and look at every item until you find the one you want.
How does a binary search work?
Repeatedly divide in half the portion of the data list that could contain the required data item. This is continued until there is only one item left in the list.
How does a bubble sort work?
Repeatedly going through the list to be sorted, comparing each pair of adjacent elements. If the elements are in the wrong order they are swapped.
How does an insertion sort work?
Sorts one data item at a time. Takes one data item from the list and places it in the correct position in the list. This is repeated until there is no more unsorted data items in the list.
How does a merge sort work?
Stage 1:
The list is successively divided in half, forming two sublist, until each sublist of length: one.
Stage 2:
Each pair of sublists is repeatedly merged to produce new sorted sublists until there is only one sublist remaining. This is the sorted list.
What are the 3 constructs used to write algorithms in pseudocode?
Sequence
Selection
Iteration
What is a sequence?
Writing the steps down in the order that they need to happen.
What is selection?
When the program will only run if the condition is met.
What is iteration?
a loop (while, for)
