Flashcards in Searching and sorting algorithms Deck (21)
When is a linear search used?
It is used to search a list of a list when the items are unsorted
How is an item found in a linear search?
Starting with the first item in the list, it checks whether this is the item it's searching for, if not it checks the next item. It does this until the item is found or until it reaches the end of the list.
What is the maximum number of items that would have to be examined to find a specific item in a linear search of a million items?
Maximum number would be 1 million searches
What is the average number of items that would have to be examined to find a specific item in a linear search of a million items?
Half so 500,000 (five hundred thousand)
What is the time complexity of a linear search?
In the worst case scenario, it's O(n)
What is the most efficient type of search algorithm and why?
A binary search is more efficient because it has a faster time complexity.
How is an item found in a binary search?
- Find the middle item in the list, if this is the midpoint stop
- If not, compare the sought after item with the middle item. If it comes before the middle item, discard the second half of the list. If it comes after the middle item, discard the first half of the list
- Repeat the first three steps on this smaller list until the sought after item is found.
When is a binary search used?
When the list is sorted
What is a binary search an example of?
A divide and conquer algorithm
What is the time complexity of a binary search?
What 3 variables are used in binary searches?
First, last and midpoint
How is the maximum number of nodes that need to be searched determined in a binary tree search?
The maximum number of nodes that need to be traversed depends on the amount of layers in the tree traversal.
If there are 4 layers (including the root node) the maximum number of nodes that need to be traversed is 4
What are the steps of a bubble sort for an array of n items?
- Go through the array comparing each item with the one next to it. If it is greater, swap them.
- The last item in the array will be in the correct place after the first pass.
- Repeat the first step n-1 times reducing the number of items to be examined by one on each pass
Which is the simplest sort and search algorithms to code
- Linear search algorithm
- Bubble sort algorithm
What is the time complexity of a bubble sort?
It's O(n^2) due to its use of a nested for loop
What is a merge sort an example of?
A divide and conquer algorithm
When is a merge sort used?
When there is a large amount of items in the list
What are the steps of a merge sort for an array of n items?
- Divide the list into n sublists each containing one element
- Repeatedly merge sublists to produce new sorted sublists (by comparing the items in each sublist) until there is only one sublist remaining. This is the sorted list
What is the time complexity of a merge sort?
There are n sublists to be merged so it has a time complexity : O(nlogn)
What is space complexity?
The amount of resources such as memory that an algorithm requires.