Sorting

Question 1

Bubble Sort time and space complexity

Answer 1

Time O(n^2), Space O(1)

Question 2

Timsort time and space complexity

Answer 2

Time O(n log(n)), Space O(n)

Question 3

what is the property of a heap?

Answer 3

heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2]

https://runestone.academy/runestone/books/published/pythonds/Trees/BinaryHeapImplementation.html

Question 4

how does bubble sort work and what’s the complexity?

Answer 4

Bubble sort is probably the least efficient sorting algorithm with time O(n^2) and space O(1). Because it can be easily done in place.

Question 5

how does quick sort work and what’s the complexity?

Answer 5

quick sort works by splitting the list into two, and then picking a partition point, and then swapping items until the partition condition is met, which is that all values <= to the partition come before the partition, and that all values > partition come after. How you pick the partition has a big impact on the performance in different cases.

Performance
Time O(n log n), Space O(log n)

Question 6

how does merge sort work and what’s the complexity?

Answer 6

The basic algorithm is recursive, and breaks the list to be sorted into halves, sorts each half, then merges the result.

Time O(n log n), Space (worst) O(n)

Merging in place could use a deque, or you could use the merge function from heapq.