$1.(12\%)$ Answer True or False to the following problems.

$(1)$ Quick sort should NOT be used when the data is almost sorted. $\_\_\_\_\_\_\_\_\_\_$

$(2)$ Quick sort is always quick. $\_\_\_\_\_\_\_\_\_\_\_\_$

$(3)$ Merge sort requires extra space. $\_\_\_\_\_\_\_\_\_\_\_$

$(4)$ Selection sort recognizes if the values are already sorted. $\_\_\_\_\_\_\_\_\_\_$

$(5)$ Binary searching is always faster than linear searching. $\_\_\_\_\_\_\_\_\_\_$

$(6)$ HeapSort is inherently unstable. $\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$2.(12\%)$ Show the contents of the array

After each of the first two iterations of

$(1)$ Selection Sort

$(2)$ Bubble Sort

$(3)$ Insertion Sort

$3.(8\%)(1)$ Show how the values in the array in Problem $2$ would have to be rearranged to satisfy

the heap property.

$4371023184195$

$01234567$

$01234567$