sort algo Flashcards

1
Q

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

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

linear is faster as recursion incurs extra overhead through function calls

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

why bubble sort?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

how to optimise bubble sort

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

requirement of merge sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

how to optimise quick sort?

A

use median as pivot

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly