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

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

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. Merge left and right subarrays into sorted array

Merge function

1. Initialise sorted array
2. Compare first elements of left & right subarray.
3. Take the smaller/greater first element into the sorted array and advance to the next element; repeat from Step 2
4. Concatenate remaining elements to the end of sorted array

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

What is the time complexity for an Insertion Sort?

Answer 5

O(n²)

Question 6

What is the time complexity for a Quick Sort?

Answer 6

O(n log n)

Question 7

Under what circumstances is the quicksort least efficient?

Answer 7

When the provided list is nearly sorted or already sorted (pivot is not median value).

Question 8

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

Answer 8

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

Question 9

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

Answer 9

The size of the given array.

Question 10

What is the time complexity for a Bubble Sort?

Answer 10

O(n²)

Question 11

What is the time complexity for a Merge Sort?

Answer 11

O(n log n)