3.1+3.2 Flashcards
What is linear search?
Linear search is for when the data is unsorted and runs through every single item.
What is binary search?(2)
Binary search is performed when a list is sorted and is much more efficient than linear search.
It works by repeatedly dividing in half the portion of the data list.
What are the differences between linear and binary search?
Linear search is very inefficient for a large number of items, the average time taken to search 1000 items will be 100 times longer than the time taken to search 10 items. However, linear search can be done on an unsorted list.
In contrast the binary search algorithm is extremely efficient. In a list of 10 million items, only 24 items would need to be examined.
What is bubble sort?(2)
Bubble sort works by repeatedly going through the list to be sorted comparing each pair of adjacent elements.
Bubble sort is much less efficient and slower than Merge sort on average.
What is merge sort?(2)
Two stage sort. Divides list in half and then divides each half in half again so on. This is done until there are only 2 items in each sublist.
These are then compared and then the sublist are put back together.
Takes up additional storage than bubble sort.
Algorithm is more difficult to code.
Define an algorithm.
An algorithm is a sequence of steps to be followed in order to complete a task.
Define decomposition.
Decomposition is the breaking of a problem into a number of smaller problems that are more manageable.
Define abstraction
Abstraction is the process of removing unnecessary detail from a problem in order to help solve it.
What is a subroutine and why are they used?(2)
A subroutine is a named, self-contained section of code performing a specific task.
These are useful because a piece of code that may appear multiple times in a programme will only have to be written and debugged once. They also make program structure clear.
Modules written in programmes can also be easier to maintain and reused in future programmes.
What are the two types of subroutines?
Procedures and functions.
What is algorithm efficiency?
Efficiency looks at how much time it takes to run a particular algorithm and how much memory is needed.
What makes algorithms more efficient?(2)
Fewer steps of code are executed. The program will take less time to complete.
Less memory is used, for example due to less variables used or fewer lines of code.
