sorting

Question 1

insertion sort facts

Answer 1

best O(n)
average and worst O(n^2)
stable
in place

Question 2

selection sort facts

Answer 2

O(n^2) across the board
not stable
in place

Question 3

heapsort facts

Answer 3

O(n log n) across the board
not stable
in place

Question 4

merge sort facts

Answer 4

O(n log n) across the board
stable
not in place

Question 5

quick sort facts

Answer 5

the one that uses a pivot point and recursion/subarrays
best and average O(n log n)
worst case O(n^2)
not stable
in place

Question 6

stable sorting

Answer 6

If a sort guarantees the relative order of equal items stays the same,
then it is a stable sort

Question 7

In Place Sorting

Answer 7

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

The amount of extra space required to sort the data is constant with
the input size.

Question 8

bucket sort facts

Answer 8

O(n + k) across the board
n is the number of elements
k is the number of buckets

Question 9

counting sort facts

Answer 9

O(n + k) across the board
n is the number of elements
k is range of elements

stable but not in place

Question 10

radix sort facts

Answer 10

O(d * n) across the board
n is the number of items
d is the number of digit keys

not in place