Quicksort

Question 1

Stable Sorting

Answer 1

If the same element is present multiple times, then they retain the original relative order of positions.

Question 1

In place sorting

Answer 1

Sorting of a data structure does not require any external data structure for storing the intermediate steps.

Question 2

Quicksort is ___, but not ___.

Answer 2

In place, but not stable.

Question 3

Mergesort is ___, but not in place.

Answer 3

Stable, but not in place.

Question 4

Quicksort Worst Case

Answer 4

θ(n^2)

Question 5

Quicksort Best Case Partitioning

Answer 5

T(n) = θ(n log n)

Question 6

Quicksort Average Case

Answer 6

θ(n log n)

Question 7

Pivot Selection Strategies

Answer 7

First or Last Element
Random
Median of 3 (left, right, and center)
Median of Medians.

Question 8

Do not use quicksort recursively for:

Answer 8

arrays of size smaller than some threshold.