2.3.1 - Algorithms Flashcards
What are the pros and cons of a bubble sort?
Pros
- Okay for smaller data sets
Cons
- Inefficient for larger data sets.
- Very inefficient for reversing the order of a data set.
- The most inefficient algorithm of the sorts studied in the course.
What is the purpose of the temp variable in a bubble sort?
Allows you to swap two values without overwriting one of them.
What is the purpose of the swapsMade Boolean?
When the algorithm reaches the end of a pass, if the Boolean is true then the list may not be sorted, so it needs to make at least one more pass.
If the end of the pass is reached and it is false, then then you have gone through the list, made no changes, so the list is sorted.
Show the steps of a bubble sort on the following array - clearly label the passes.
[95, 10, 5, 33, 100, 77, 45]
Describe the steps of a bubble sort on an array.
- Compares each pair of data
- If they are in the correct order it moves to the next pair
- If they are in the wrong order it swaps them
- Continues to the end of the array
- If there has been a swap it checks again
- If there have been no swaps then it is sorted
Describe how an insertion sort works
- Splits the list into sorted and unsorted
- The first item in the list is classed as sorted
- Insert one number at a time from the unsorted list into correct position by moving backwards through the list of sorted numbers
What are the pros and cons of the insertion sort?
- (+) Simplest Sort to code
- (+) One of the fastest algorithms for sorting very small arrays
- (-) Impractical for sorting large arrays.
Show the steps of an insertion sort on the following array
[95, 10, 5, 33, 100, 77, 45]
Describe how a linear search works
Start at the first element, if equal to search item, then report found
If not equal, then move to next element
Repeat for all elements until found or the end of the list reached
What are the pros and cons of a linear search?
- (+) Can work on both ordered and unordered data sets
- (+) Can have multiple processors searching different areas at the same time.
- (+) Scales very with additional processors
- (-) If the item is not in the list, then all items will be searched, this makes is a slow algorithm for large lists.
Describe a binary search
- Find mid-point, if equal to mid-point then report found
- If less than mid-point then make sub-list from left
- If greater than mid-point then make sub-list from right
- Repeat with sub-list until found or sub-list is empty
Describe the technicalities of a binary search
- Calculate array midpoint by adding the array lower bound to the array upper bound, using the DIV command divide it by 2 (equivalent to rounding down)
- Compare array midpoint with value to search for, if equal set found flag to true
- if array midpoint < value to search for, change lowerbound to equal midpoint + 1
- if array midpoint > value to search for, change upperbound to equal midpoint – 1
- Repeat until lowerbound is greater than or equal to upperbound
Demonstrate a binary search on the following array to find the value 47
[4, 7, 8, 21, 46, 47, 51]
- Find the mid-point in the list: 21 (index 3)
- Compare it to the value 47, match = false
- 47 is greater than middle point, so new subset is 46-51
- Find the middle of the new subset (47 index 5)
- Is this value equal to 47, true Search finishes
Describe the pros and cons of a binary search
- (-) Only works on an ordered set of data
- (+) Halves the list each time so works well on large data sets
- (+) Efficient as does not need to search every single element/uses divide and conquer
