2017 Flashcards
Max comparisons in a binary search
Finding power of two greater than items in the list
Eg List size 5 2^3=8 so 3 is answer
No of comparisons in a linear search
N/2 (n is number of items in the list)
Linear Search facts
Simple algorithm
List may be unsorted
Number of comparisons given by n/2
Slow for large lists
Binary Search facts
Complex algorithm
List must be sorted
Max comparisons given by power of two greater than items in list eg 5 items would be 2^3=8 so 3 is answer
Fast for large lists
Why selection sort two lists is inefficient
Has to check every item from list every time loop executes
Requires second list with same storage space as first= problem if large list being sorted
Comparing Binary and Linear Search
Binary search requires list to be sorted - more complex so more processor time
Linear search more efficient on smaller lists
Bubble sort facts
No additional operation memory as swaps items between positions in a list
Faster for a partially sorted list as variable can be introduced to keep track of whether swaps have occurred or not
Unconditional version will make n passes through list and n^2 comparisons
In worst case scenario - reverse order = n^2 swaps also
Number of swaps depends on how partially sorted original list is
Insertion Sort number of passes
Always n-1 where n is the number of items in the list
Outer loop goes from 1 up to number of elements
(Missing element zero)
Quick Sort facts
Recursive algorithm - Suitable for parallel processing
Memory intensive
Inefficient for sorting lists which contain lots of similar terms
Merge Sort
Divides into sorted sub lists and puts two sorted lists together to make one large sorted list
Useful if you have two sorted lists which have to be put together
Divide and Rule Algorithms
Merge sort
Quick sort
Explain why a class may have position variables and others do not
The parent class will have properties which are inherited
Explaining encapsulation in terms of certain class
Object properties would be hidden and inaccessible outside the specified class or subclass
Code within classes methods may manipulate properties of an instance of that class ie the position coordinates of that instance
Why classes may be inefficiently structured
Repetition of many lines of code ie methods and properties in multiple subclasses
How classes can be made more efficient
Create a subclass and place all common properties/methods in here Create two new subclasses of this subclass with only their unique property
