4.2 Quicksort

Question 1

Aim of quicksort

Answer 1

Divide and conquer algorithm that works in situ

Question 2

Is quickSort a stable algorithm

Answer 2

No

Question 3

What is the worst case runtime complexity of quickSort?

Answer 3

n(n-1)/2 = theta(n^2)

Question 4

Is quickSort in situ

Answer 4

Yes ( sort of, has to store m)

Question 5

Best case runtime complexity for quickSort?

Answer 5

theta(nLog(n))

Question 6

Average expected runtime complexity for quickSort?

Answer 6

theta(nLog(n))