Chapter 5

Question 1

What is searching?

Answer 1

Looking through a file to see if a particular piece of data exists

Question 2

What is sorting?

Answer 2

Putting items of data into a particular order - alphabetical or numerical.

Question 3

What is bubble sort?

Answer 3

An algorithm to sort an unordered list by comparing adjacent items and swapping them if needed.

Question 4

How does bubble sort work?

Answer 4

1) Start at the beginning of the list.
2) Compare the first and second values. Swap if necessary.
3) Compare the second and third values. Swap if necessary.
4) Continue working up the list untill the end.
5) If the list still isn’t sorted, start the next pass by going to the beginning.
6) extra pass to check

Question 5

Advantages of bubble sort (2)

Answer 5

Simplest

easiest to code

Question 6

Disadvantages of bubble sort (1)

Answer 6

Slowest

Question 7

What insertion sort?

Answer 7

An algorithm used to sort lists by examining each item in turn and inserting it into its correct position.

Question 8

How does insertion sort work?

Answer 8

1) If there is only one item in the list then stop
2) Start with the second item and compare it to the first and swap if necessary
3) compare the third and second and swap if necessary. Repeat step 2.
4) Compare the third and fourth and swap if necessary. Repeat step 3.
5) Continue till the last element.

Question 9

Advantages of insertion sort (3)

Answer 9

Simple
easy to code
Twice as fast as bubble sort

Question 10

Disadvantages of insertion sort

Answer 10

Slower than merge sort

Question 11

What is merge sort?

Answer 11

A sorting algorithm which sorts lists bu recursively dividing a list smaller and smaller untill the size of each list is one, and then add them up together while sorting them.

Question 12

How does merge sort work?

Answer 12

1) if there is only one item in the list then stop
2) Divide the list into 2 parts
3) Recursively divde these lists untill the size of each becomes one
4) Recursively merge the lists with the items in order

Question 13

Advantages of merge sort (1)

Answer 13

Fastest of the three algorithms

Question 14

Disadvantages of merge sort (2)

Answer 14

Hardest to code

Harderst on the processor

Question 15

How does linear search work?

Answer 15

Start at the beginning of the list
move through each element until you find the search criterion
or reach the end of list

Does not need the list to be sorted first

Question 16

How to calculate average number of passes for linear search?

Answer 16

1+x / 2

X = number of elements on the list

Question 17

How does binary search work?

Answer 17

• Select middle element and compare to search criterion
• If it matches, stop
• if it is lower than the search criterion, descard left half and if higher discard right half.
• Repeat until search criterion is found or the list length is one.

Requires list to be sorted

Question 18

How to find the average number of passes for binary search?

Answer 18

(Log2(x) + 1) / 2

Question 19

Which is faster on average binary or linear?

Answer 19

Binary