2.3 Algorithms Flashcards
When is a linear search used?
When items are not in an ordered sequence.
What does a linear search do?
Searches through a list one item after another until the required item is found or the end of the list is reached.
What is a benefit of a linear search?
It is very simple
Can search unordered lists
What is a con of a linear search?
It is inefficient, especially for long lists.
What does a binary search do?
Divides the area of where the item could be by two.
Finds the middle item of the list and removes one half depending if the middle item is bigger or smaller than the required item.
Continues to half list until item is found as middle number or one item is left.
When is a binary search used?
When a list is ordered.
Why is it important to sort data in processing?
Because it is more efficient to search an ordered list than an unordered one.
What is a benefit of a binary search?
It is more efficient than a linear search
What is a con of a binary search?
It can only be used on a sorted list.
What do both linear and binary searches use to know which item they are looking at in a list?
An index
What is bubble sorting?
Going through a list and comparing the first two values, and ordering them. Then moving onto the next pair and ordering them. Repeat until the list is sorted.
Which value will be sorted after the first pass of a bubble sort?
The last value of a list.
What is insertion sorting?
The first item from the unsorted list is not moved. The second item is then removed and the first item is either moved or not depending on whether it is bigger or smaller than the item that was removed. The removed item is then inserted into the empty space. This continues with the sorted items moving to create the correct space for the unsorted item to be inserted into.
What is a benefit of bubble sorting?
It is very simple and easy to understand.
What is a con of bubble sorting?
It is very inefficient as it requires lots of passes.