### Chapter 17 Sorting

Section 17.2 Bubble Sort

*17.1*Suppose a list is [2, 9, 5, 4, 8, 1]. After the first pass of bubble sort, the list becomes

*17.2*The best-time complexity for bubble sort is _____________.

*17.3*The worst-time complexity for bubble sort is _____________.

*17.4*The time to merge two sorted lists of size n is _________

*17.5*The worst-time complexity for merge sort is _________

*17.6*The average-time complexity for merge sort is _________

*17.7*What is correct about a pivot?

*17.8*Suppose you choose the first element as a pivot in the list [5, 2, 9, 3, 8, 4, 0, 1, 6, 7]. Using the partition algorithm in the book, what is the new list after the partition?

*17.9*The worst-time complexity for quick sort is _________

*17.10*The average-time complexity for quick sort is _________

*17.11*Which of the following statements are true?

*17.12*To remove the root, you need to start a process by first placing _______ to the place of the root and move it down to maintain the heap property.

*17.13*To add a new node, you need to start a process by first placing it as _______ and move it up to maintain the heap property.

*17.14*A heap is represented using a list. Is the list [1, 2, 4, 5, 9, 3] a heap?

*17.15*A heap is represented using a list. Is the list [64, 42, 59, 32, 39, 44] a heap?

*17.16*The worst-time complexity for heap sort is _________

*17.17*The average-time complexity for heap sort is _________

*17.18*The most efficient algorithm for sorting integer keys is __________.

*17.19*The __________ algorithm does not compare keys.