2.3.1 - Algorithms (Searches and Sorts)

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?

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

[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

Describe how an insertion sort works

Answer 6

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

What are the pros and cons of the insertion sort?

Answer 7

(+) Simplest Sort to code
(+) One of the fastest algorithms for sorting very small arrays

(-) Impractical for sorting large arrays.

Question 8

Show the steps of an insertion sort on the following array

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

Answer 8

Question 9

Describe how a linear search works

Answer 9

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

If not equal, then move to next element (incrementally)

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

Question 10

What are the pros and cons of a linear search?

Answer 10

(+) 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 11

Describe a binary search

Answer 11

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

Describe the technicalities of a binary search

Answer 12

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

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

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

Answer 13

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

Describe the pros and cons of a binary search

Answer 14

(-) 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 15

Demonstrate a Merge Sort on the following array

[7, 3, 2, 16, 24, 4, 11, 9]

Answer 15

Question 16

What are the cons of Merge Sort?

Answer 16

(+) More efficient with larger volumes of data to sort
(-) May require more memory space as the elements increase
(-) Might create a new array each time it splits and merges
(-) Often implemented recursively which places additional data on the stack

Question 17

Describe the steps of a Merge Sort

Answer 17

• Splits the list in half repeatedly until it is in independent arrays
• Compare the first two items (index 0 and 1)
• Combine to create a new array in ascending order
• Repeat with indexes 2 and 3, then 4 and 5
• Compare the first element in the first two new arrays
• Choose the largest element, writing this to the new array first
• Repeat until no elements left
• Combine the two remaining lists into one list

Question 18

Perform a Quick Sort on the following array

[42, 83, 27, 18, 52]

Answer 18

• Pick a number as the pivot (42)
• Create two sub lists of those elements greater and those less than the pivot. (27 and 18 | 83 and 52) without attempting to order within the sub lists.
• Pick a number as the pivot of the left list (27)
• Create two sub lists of those elements greater and those less than the pivot.
• Pick a number as the pivot of the right list (83)
• Create two sub lists of those elements greater and those less than the pivot.
• Repeat until all items have been a pivot

Question 19

What are the pros and cons of Quick Sort?

Answer 19

(+) Very quick for large sets of data
(+) Produces the most effective and widely used method of sorting a list of any item size

(-) Initial arrangement of data affects the time taken.
(-) Harder to code
(-) Often implemented recursively which places additional data on the stack