Sort and Search Algorithms

Question 1

A search algorithm is

Answer 1

a set of instructions for finding a specific item of data within a data set.

Question 2

An effective search is

Answer 2

one which will always either find the solution or determine that the target data is not present

Question 3

An efficient search will

Answer 3

find the solution quickly regardless of its location within the data set

Question 4

two common search algorithms are:

Answer 4

Linear search and Binary search

Question 5

Linear search

Answer 5

checks each term in a dataset one by one until output is found

Question 6

pros and cons of linear search

Answer 6

pro: Very easy to implement

con: Slow on a long list

Question 7

Binary Search

Answer 7

Looks at the middle value of a dataset, if that value is greater than the target, repeat on the first half of the data set, if it is less than the target, repeat on the second half of the data set. Stop repeating when target is found or the size of our dataset is zero

Question 8

pros and cons of binary search

Answer 8

pro: faster than linear search on a large dataset
cons: Dataset must be sorted before starting

Question 9

which search algorithm only works on sorted lists and which works on unsorted lists

Answer 9

sorted: linear search
unsorted: binary search

Question 10

examples of sort algorithms:

Answer 10

bubble sort, insertion sort and merge sort

Question 11

A sort algorithm is

Answer 11

a set of instructions to arrange a dataset into a particular order.

Question 12

An efficient sort algorithm is

Answer 12

one which can sort a dataset in a short time.

Question 13

bubble sort

Answer 13

compares the first two items in a dataset and swaps them if they are in the wrong order. This process continues for the rest of the dataset. Repeat the whole process until a pass with no swaps happens.

Question 14

What is a pass?

Answer 14

A pass is when every item in a dataset has been tested and the end of the dataset has been reached

Question 15

pros and cons of bubble sort

Answer 15

pros: easy to implement, does not use much memory
cons: poor for efficiency

Question 16

insertion sort

Answer 16

in a dataset, compare second item with first, swap if necessary. take the third item and compare with second and first item. compare items with the previous items: 2 with 1; 3 with 2 and 1; 4 with 3,2 and 1; 5 with 4,3,2 and 1 etc. repeat until sorted list

Question 17

pros and cons of insertion sort

Answer 17

pros: easy to implement, little memory used
cons: not very efficient

Question 18

Merge sort is an example of

Answer 18

a divide and conquer algorithm

Question 19

merge sort

Answer 19

split lists into lists of size one
merge each pair of sublists
continue merging until there is only one list

Question 20

is merge sort or insertion sort more efficient?

Answer 20

merge sort is more efficient than insertion sort