# Searching and sorting algorithms Flashcards

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?

It’s O(logn)

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