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

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 new array
2. Compare first elements of left & right subarray.
3. Pop the smaller/greater first element into array from (1); repeat from Step 2
4. Concatenate remaining elements to the end of array from (1)

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)

Question 12

memory space (in-place vs out-of-place)

Answer 12

1. an in-place implementation does not need additional data structures in its implementation
2. an out-of-place implementation initializes a new array (or other data structure) fro storing sorted elements

Question 13

linear vs recursion

Answer 13

1. linear algorithm is usually faster than recursive algorithm since recursion incurs extra overhead through function calls
2. however its iterative nature requires all processing to be done on a single process thread with no opportunity for multiple threads to speed up the work

while recursive function by nature consists many self contained tasks which can be divided among many threads

Question 14

bubble sort optimisation

Answer 14

1. skips sorted elements
2. final iteration can be skipper since only first element is unsorted
3. no swaps are made subsequent iterations may be skipped

Question 15

insertion sort optimisation

Answer 15

1. target should be moved to the insertion point as efficiently as possible
2. terminate index search once an insertion index is found

Question 16

optimisation for merge sort

Answer 16

1. minimisation of modification
   additional indices used to track position of elements in left and right array

Question 17

optimisation of quicksort

Answer 17

median item as pivot