Sorting Properties

in-place; less; n; structure; not

A sorting algorithm is __________ (which measure space complexity) if it uses _____ than O(______) auxiliary memory. In other words, a sorting algorithm uses the same data structure as the _______ structure (it does _____ use an additional data structure)

adaptive

A sorting algorithm is ________ if it takes advantage of data being partially or totally sorted

stable

A sorting algorithm is ________ if items with the same value stay in the same relative order (left item comes before right item)

yes; yes; yes

Is Bubble Sort:

• Stable: ______

• Adaptive: _____

• In-Place: _______

yes; yes; yes

Is Cocktail Shaker Sort:

• Stable: _____

• Adaptive: ____

• In-Place: _____

yes; yes; yes

Is Insertion Sort:

• Stable: _____

• Adaptive: _____

• In-Place: _____

no; no; yes

Is Selection Sort:

• Stable: _____

• Adaptive: _____

• In-Place: _____

no, no; no; yes

Is Heap Sort:

• Stable: ____

• Adaptive: _____

• In-Place: _____ (if used a heap) or ______ (if you do heap logic yourself)

yes; no; no

Is Merge Sort:

• Stable: _____

• Adaptive: ______

• In-Place: ______

no; no; yes

Is Quick Sort:

• Stable: ____

• Adaptive: _____

• In-Place: _____

yes; no; no

Is Radix Sort:

• Stable: ____

• Adaptive: _____

• In-Place: _____

no; yes

Is QuickSelect:

• Stable: ______

• In-Place: ______