2.3.1 Algorithms

Question 1

What are the pros and cons of a bubble sort?

Answer 1

Pros

• Okay for smaller data sets

Cons

• Inefficient for larger data sets.
• Very inefficient for reversing the order of a data set.
• The most inefficient algorithm of the sorts studied in the course.

Question 2

What is the purpose of the temp variable in a bubble sort?

Answer 2

Allows you to swap two values without overwriting one of them.

Question 3

What is the purpose of the swapsMade Boolean in a bubble sort?

Answer 3

When the algorithm reaches the end of a pass, if the Boolean is true then the list may not be sorted, so it needs to make at least one more pass.

If the end of the pass is reached and it is false, then then you have gone through the list, made no changes, so the list is sorted.

Question 4

Show the steps of a bubble sort on the following array - clearly label the passes.

[95, 10, 5, 33, 100, 77, 45]

Answer 4

Question 5

Describe the steps of a bubble sort on an array.

Answer 5

• Compares each pair of data
• If they are in the correct order it moves to the next pair
• If they are in the wrong order it swaps them
• Continues to the end of the array
• If there has been a swap it checks again
• If there have been no swaps then it is sorted

Question 6

Write / describe the pseudocode for a Bubble Sort

Answer 6

Question 7

Describe how an insertion sort works

Answer 7

• Splits the list into sorted and unsorted
• The first item in the list is classed as sorted
• Insert one number at a time from the unsorted list into correct position by moving backwards through the list of sorted numbers

Question 8

What are the pros and cons of the insertion sort?

Answer 8

• (+) Simplest Sort to code
• (+) One of the fastest algorithms for sorting very small arrays
• (-) Impractical for sorting large arrays.

Question 9

Show the steps of an insertion sort on the following array

[95, 10, 5, 33, 100, 77, 45]

Answer 9

Question 10

Write / describe the pseudocode for an Insertion Sort

Answer 10

Question 11

Describe how a linear search works

Answer 11

Start at the first element, if equal to search item, then report found

If not equal, then move to next element

Repeat for all elements until found or the end of the list reached

Question 12

What are the pros and cons of a linear search?

Answer 12

• (+) Can work on both ordered and unordered data sets
• (+) Can have multiple processors searching different areas at the same time.
• (+) Scales very with additional processors
• (-) If the item is not in the list, then all items will be searched, this makes is a slow algorithm for large lists.

Question 13

Write / describe the pseudocode for a Linear Search

Answer 13

Question 14

Describe a binary search

Answer 14

• Find mid-point, if equal to mid-point then report found
• If less than mid-point then make sub-list from left
• If greater than mid-point then make sub-list from right
• Repeat with sub-list until found or sub-list is empty

Question 15

Describe the technicalities of a binary search

Answer 15

• Calculate array midpoint by adding the array lower bound to the array upper bound, using the DIV command divide it by 2 (equivalent to rounding down)
• Compare array midpoint with value to search for, if equal set found flag to true
• if array midpoint < value to search for, change lowerbound to equal midpoint + 1
• if array midpoint > value to search for, change upperbound to equal midpoint – 1
• Repeat until lowerbound is greater than or equal to upperbound

Question 16

Demonstrate a binary search on the following array to find the value 47

[4, 7, 8, 21, 46, 47, 51]

Answer 16

• Find the mid-point in the list: 21 (index 3)
• Compare it to the value 47, match = false
• 47 is greater than middle point, so new subset is 46-51
• Find the middle of the new subset (47 index 5)
• Is this value equal to 47, true Search finishes

Question 17

Describe the pros and cons of a binary search

Answer 17

• (-) Only works on an ordered set of data
• (+) Halves the list each time so works well on large data sets
• (+) Efficient as does not need to search every single element/uses divide and conquer

Question 18

Write / describe the pseudocode for a Binary Search

Answer 18

Question 19

Write the pseudocode to push an item to a stack

Answer 19

Question 20

Write the pseudocode to pop an item to a stack

Answer 20

Question 21

Keywords to describe a queue

Answer 21

• Dynamic Data Structure
• Enqueue
• Dequeue
• First in First Out
• Peek
• Front Pointer
• Rear Pointer
• Circular / Non-Circular

Question 22

Keywords to describe a stack

Answer 22

• Dynamic Data Structure
• Pop
• Push
• First in Last Out (LIFO)
• Peek
• Top Pointer

Question 23

Write the pseudocode to dequeue an item to a queue

Answer 23

Question 24

Write the pseudocode to enqueue an item to a queue

Answer 24

Question 25

Describe the purpose of the **front** and **rear** pointer in a queue

Answer 25

* **Front/Head** - Used to identify the first item in the queue i.e the one to dequeue next * **Rear/Tail**- Used to identify the next free space in the queue i.e. the next element to be enqueued

Question 26

Give examples of where **stacks** and **queues** are used in computers

Answer 26

**Queues** - Used in print queues – New print jobs are added to the end of the queue. Jobs are processed from the front of the queue **Stack** - Internet History – When you visit a site the last site is pushed to the stack. When you click back the last item is popped from the stack, and then loaded.