Algorithms (2.1) Flashcards
1
Q
What is a linear search
A
- searches for the target value on ANY list (ordered/unordered) in a sequence starting from the first value and going through the list until it finds the target (returns true) or the list is complete (returns false)
- (goes through every value in the list)
2
Q
What are the positives of linear searches
A
- Linear search is easier to understand than binary and works on any list
3
Q
What are the negatives of linear searches
A
- much more inefficient when searching longer lists compared with binary search
4
Q
What is a binary search
A
- Divides the list in 2, checks the midpoint to see if its the correct value, if not it will check if the value is higher or lower than midpoint, if higher it will take the right side of the list and find the midpoint and repeat the process
- same process if the value is lower, but it will check the left side
- only works for sorted lists
- MIDPOINT = (LowestIndex + HighestIndex) DIV 2
5
Q
What are the positives of binary searches
A
- Binary search is more efficient with longer lists than linear search
6
Q
What are the negatives of binary searches
A
- it is harder to understand and can only work on sorted lists.
7
Q
What is insertion sort
A
- simplest sorting algorithm which arrives at the final sorted list, by inserting each value in its correct place from left to right (values are inserted towards left only)
8
Q
What are the positives of insertion sort
A
- Insertion sort is the simplest sorting algorithm to understand
9
Q
What are the negatives of insertion sort
A
- it is very time consuming and ineffective with longer lists
10
Q
What is bubble sort
A
- sorts the values by comparing two values at a time and swapping them if they are not in order. Repeat process until you have gone through the values (this is called a pass). When the required value is at the end, start back from the beginning. Only stops when a pass returns 0 swaps
11
Q
What are the positives of bubble sort
A
- easier to understand than merge sort
12
Q
What are the negatives of bubble sort
A
- very inefficient when sorting longer lists/datasets
13
Q
What is a merge sort
A
- divide the dataset into smaller sub-sets (halving each time until you end up with individual values). Then compare subset values and re-order in correct order, merging each subset until you reach the full dataset (in order)
14
Q
What are the positives of a merge sort
A
- Merge sort is more efficient than the bubble and insertion sort with longer lists
15
Q
What are the negatives of a merge sort
A
- is more difficult to understand and uses more memory
