General Algorithms

Question 1

What does it mean for an algorithm to be stable

Answer 1

two items of the same value are not swapped

Question 2

what does it mean for an algorithm to be inplace

Answer 2

it uses no extra memory

Question 3

explain the Partition step in quick sort

Answer 3

Set a variable i for the index of the most recently found value lower than the pivot (update everytime you find a new value lower)

loop through the list placing items lower at i+1 and update i
leave items larger alone

then swap the value at i+1 with the pivot (typically the last value)

Question 4

what is sterlings approximation

Answer 4

n! = sqrt(2pi n)(n/e)^n