sort algo Flashcards
compare in-place (bubble, insertion) & out-of-place (merge, quick) characteristic of sort algo
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)
compare linear (bubble, insertion) & recursive (merge, quick) characteristic of sort algo
linear is faster as recursion incurs extra overhead through function calls
why bubble sort?
can skip sorted elements (last element) (if almost all elements are sorted, bubble sort tends towards time efficiency of O(n))
how to optimise bubble sort
- 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)
requirement of merge sort
subarrays are assumed to be sorted (lowk idk how this helps)
how to optimise quick sort?
use median as pivot
why A algo used instead of B algo tho they hv the same t efficiency?
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)