sort algo

Question 1

compare in-place (bubble, insertion) & out-of-place (merge, quick) characteristic of sort algo

Answer 1

in-place: dn additional data structures in its implementation
out-of-place: initialises a new array for storing sorted elements (:. require more memory space due to extra memory needed to hold new array)

Question 2

compare linear (bubble, insertion) & recursive (merge, quick) characteristic of sort algo

Answer 2

linear is faster as recursion incurs extra overhead through function calls

Question 3

why bubble sort?

Answer 3

can skip sorted elements (last element) (if almost all elements are sorted, bubble sort tends towards time efficiency of O(n))

Question 4

how to optimise bubble sort

Answer 4

• after each iteration, the largest element is at the end of the array hence, inner loop can exclude the largest element of the iteration (eg. for j in range(len(array) - i)
• in any iteration, if there are no swaps made (array sorted), the subsequent iterations can be skipped (eg. using a sentinel val like swapped = False)

Question 5

requirement of merge sort

Answer 5

subarrays are assumed to be sorted (lowk idk how this helps)

Question 6

how to optimise quick sort?

Answer 6

use median as pivot

Question 7

why A algo used instead of B algo tho they hv the same t efficiency?

Answer 7

time efficiency measures how the execution time grows with the size of input data / not indicative of actual t :. A algo still faster than B (across all sizes)