Sort algorithms

Question 1

The key steps for Bubble Sort are:

Answer 1

1. Iterate through each pair of elements (i, i+1)
2. Compare them; swap them if not in the desired order
   (largest/smallest element should be at end of array after first iteration)
3. Repeat for subsequent iterations, excluding the most recently sorted value

Question 2

The key steps for Insertion Sort are:

Answer 2

1. Assume the first element is sorted.
2. Iterate through each subsequent element (in the unsorted subarray): this is the target.
3. Determine the most appropriate place in sorted subarray to insert the target element
4. Carry out the insertion using pop/insert

Question 3

The key steps for Merge Sort are:

Answer 3

1. Handle the base case (empty/single-element array)
2. Split the array into left and right subarrays
3. Recursively sort the left and right subarrays
4. Pass left and right subarrays to merge function to obtain sorted array

Merge function

1. Initialise empty array (arr)
2. Check if left or right subarrays are empty; if either is empty, return arr + left + right
3. If both are not empty, compare first elements of left & right subarray.
4. Pop the smaller/greater first element into arr; repeat from Step 2

Question 4

The key steps for Quick Sort are:

Answer 4

1. Handle the base case (empty/single-element array)
2. Select pivot (can use last element)
3. Initialise less-than (lt) and greater-than-equal (gte) subarrays
4. Iterate through all elements except pivot; if element less than pivot, append to lt; if element greater than or equal pivot, append to gte.
5. Recursively sort lt and gte
6. Recombine lt, gte, and pivot into a single array

Question 5

Which two sorts are in-place?

Answer 5

1. Bubble Sort
2. Insertion Sort

[Merge Sort and Quick Sort are both out-of-place]

Question 6

What is the time complexity for an Insertion Sort?

Answer 6

O(n^2)

Question 7

Under what circumstances is the quicksort most suboptimal?

Answer 7

When the provided list is nearly sorted or already sorted.

Question 8

What is the time complexity for a Quick Sort?

Answer 8

O(n log n)

Question 9

What does it mean when a sorting algorithm is said to be ‘stable’?

Answer 9

A stable sorting algorithm ensures that elements with identical sorting properties still maintain their original order.

Question 10

What is the key determining factor that affects the execution time of a sort algorithm?

Answer 10

The size of the given list.