Sorting and Searching Algorithms

Question 1

What are the 3 components of a Bubble sort?

Answer 1

• Outer loop: Loops through the list until no swaps have been made
• Inner loop: Loops through every item in the array
• If-statement: Compares 2 items and swaps if first is greater than second

Question 2

What is the Big O efficiency of a Bubble sort?

Answer 2

O (n^2)

Question 3

Why are Bubble sort algorithms inefficient?

Answer 3

They require multiple loops through data that has already been sorted

Question 4

How does a Binary search work?

Answer 4

• Choose a midpoint and divide data into two halves
• If the key is smaller than the midpoint, delete the right half
• if the key is larger than the midpoint, delete the left half
• repeat until item is found or there are no data items remaining

Question 5

What is the Big O efficiency of a Binary search?

Answer 5

O (log n)

Question 6

How does the partition step of a Quicksort work?

Answer 6

• A pivot value is chosen
• If the rightmost value is larger than the pivot, the next item is compared
• If the rightmost value is smaller than the pivot, the two numbers are swapped.
• After a swap, the next item after the swapped item on the side closest to the pivot will be compared
• After all swaps have been completed, the pivot value will never be swapped again as it has been sorted

Question 7

How does the recursive step of a Quicksort work?

Answer 7

• Repeat the partition step on all items to the left of the pivot
• Repeat the partition step on all items to the right of the pivot

Question 8

What swaps would occur if a quicksort was used on this set of numbers? Take 15 as the pivot value

15, 32, 4, 7, 89, 12, 69

Answer 8

• 12, 32, 4, 7, 89, 15, 69
• 12, 15, 4, 7, 89, 32, 69
• 12, 7, 4, 15, 32, 69

Question 9

What is the Big O efficiency of a Quicksort

Answer 9

0 (n log n)

Question 10

What is the Big O efficiency of a linear search?

Answer 10

O (n)

Question 11

How does adding a sentinel value to a linear search increase the efficiency?

Answer 11

Guarantees the search item is found, so eliminates the need to check if the end of the list has been reached.