Searching and sorting algorithms

Question 1

When is a linear search used?

Answer 1

It is used to search a list of a list when the items are unsorted

Question 2

How is an item found in a linear search?

Answer 2

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.

Question 3

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?

Answer 3

Maximum number would be 1 million searches

Question 4

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?

Answer 4

Half so 500,000 (five hundred thousand)

Question 5

What is the time complexity of a linear search?

Answer 5

In the worst case scenario, it’s O(n)

Question 6

What is the most efficient type of search algorithm and why?

Answer 6

A binary search is more efficient because it has a faster time complexity.

Question 7

How is an item found in a binary search?

Answer 7

• 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.

Question 8

When is a binary search used?

Answer 8

When the list is sorted

Question 9

What is a binary search an example of?

Answer 9

A divide and conquer algorithm

Question 10

What is the time complexity of a binary search?

Answer 10

It’s O(logn)

Question 11

What 3 variables are used in binary searches?

Answer 11

First, last and midpoint

Question 12

How is the maximum number of nodes that need to be searched determined in a binary tree search?

Answer 12

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

Question 13

What are the steps of a bubble sort for an array of n items?

Answer 13

• 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

Question 14

Which is the simplest sort and search algorithms to code

Answer 14

• Linear search algorithm

- Bubble sort algorithm

Question 15

What is the time complexity of a bubble sort?

Answer 15

It’s O(n^2) due to its use of a nested for loop

Question 16

What is a merge sort an example of?

Answer 16

A divide and conquer algorithm

Question 17

When is a merge sort used?

Answer 17

When there is a large amount of items in the list

Question 18

What are the steps of a merge sort for an array of n items?

Answer 18

• 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

Question 19

What is the time complexity of a merge sort?

Answer 19

There are n sublists to be merged so it has a time complexity : O(nlogn)

Question 20

What is space complexity?

Answer 20

The amount of resources such as memory that an algorithm requires.

Question 21

What are the two things that are considered when determining the efficiency of an algorithm?

Answer 21

Time complexity

Space complexity