2.1.3 - Searching and Sorting Algorithms

Question 1

Types of searching algorithms

Answer 1

Linear search and Binary Search

Question 2

Does the list in a linear search have to be ordered or unordered

Answer 2

It can be either

Question 3

Does the list in a binary search have to be ordered or unordered

Answer 3

It has to be ordered

Question 4

How does a linear search work? (3 steps)

Answer 4

• The length of the list is found
• The program searches through the values in order from the start using a counter
• It stops once the required value has been found or the list ends

LESS EFFECTIVE THAN BINARY

Question 5

Hows does a binary search work? (4 steps)

Answer 5

• Finds the midpoint of the ordered list
• If the midpoint isn’t the required value then it checks if the required value is lower or higher than the midpoint
• If value is higher, it disregards all smaller numbers and if the value is lower, it disregards all larger numbers
• This repeats until the value is found

MORE EFFECTIVE THAN LINEAR

Question 6

Types of sorting algorithms

Answer 6

• Bubble sort - temp + swaps
• merge sort - sublists
• insertion sort - inserts into correct place

Question 7

Advantages and disadvantages of bubble sort

Answer 7

• Easy to understand
• However, very slow and inefficient

Question 8

Advantages and disadvantages of merge sort

Answer 8

• Very quick comparisons - better for use on large data sets than other sorting methods
• Difficult to understand and needs lots of memory
  *

Question 9

Advantages and disadvantages of insertion sort

Answer 9

• Quicker than a bubble sort
• Good for inserting extra data into already sorted lists
• Not efficient when used on large data sets

Question 10

Similarities of a bubble sort and an insertion sort

Answer 10

• Both less efficient that a merge sort
• Both produce a sorted list
• Both work from left to right’
• Both swap values
• Both have nested loops

Question 11

Difference between a bubble an insertion sort

Answer 11

• An insertion sort moves the value into its correct postition
• A bubble sort repeatdely swaps values until it is in the correct position

Question 12

Steps in a merge sort

DIVIDE AND CONQUER

Answer 12

1. The list is split into sublist and this repeats until each element has its own sublist (sublist with a length of 1)
2. Each pair of adjacent sublists is compared and combined to form an ordered sublist with length 2
3. This process is repeated until there is only one list left and the list will be ordered

Question 13

Steps in a bubble sort

Answer 13

1. Start at the fron of the list and compare the two elements
2. If they are in the righ order, don’t swap but if they aren’t swap
3. Repeat for next 2 elements and repeat until one full pass has been made
4. Repeatedly perform passes until a pass has been done and no swaps have been made

Question 14

Tips to identify the different sorting algos

Answer 14

• Bubble - look for temp + nested loop
• Insertion - nested loop + i and i-1
• Merge - lots of sublists

Question 15

Why is the nested loop used in bubble and insertion sorts condition controlled

Answer 15

• Don’t know how many swaps are needed
• Will keep swapping until in correct position