17. Sorting - 18 Questions

# 17. Sorting

18 Questions
Created by Y. Daniel Liang
Free
##### Sorting is ordering a list of objects. We can distinguish two types of sorting. If the number of objects is small enough to fits into the main memory, sorting is called internal sorting. If the number of objects is so large that some of them reside on external storage during the sort, it is called external sorting. This Python quiz is aimed at students, enthusiasts and job seekers with little or no programming experience. It aims to provide them with an understanding of the role of computers and python programming language.
1. Suppose a list is [2, 9, 5, 4, 8, 1]. After the first pass of bubble sort, the list becomes

2, 9, 5, 4, 8, 1
2, 9, 5, 4, 1, 8
2, 5, 9, 4, 8, 1
2, 5, 4, 8, 1, 9

2. The best-time complexity for bubble sort is _____________.

O(1)
O(logn)
O(n)
O(nlogn)

3. The worst-time complexity for bubble sort is _____________.

O(logn)
O(n)
O(nlogn)
O(n*n)

4. The time to merge two sorted lists of size n is _________

O(1)
O(logn)
O(n)
O(nlogn)

5. The worst-time complexity for merge sort is _________

O(1)
O(logn)
O(n)
O(nlogn)

6. The average-time complexity for merge sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

7. What is correct about a pivot?

1. A pivot divides a list into two sublists of equal size.
2. A pivot can be chosen arbitrarily.
3. A pivot divides a list into two sublists, the elements in the first list are no larger than the pivot and the elements in the second list are larger than the pivot.
4. You should always choose a pivot that divides the list evenly.

1 & 2
2 & 3
3 & 4
1 & 4

8. The worst-time complexity for quick sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

9. The average-time complexity for quick sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

10. Which of the following statements are true?

1. A heap is a complete binary tree.
2. Each node is greater than or equal to any of its children.
3. A binary tree is complete if every level of the tree is full except that the last level may not be full and all the leaves on the last level are placed left-most.
4. A heap is a full binary tree.

1, 2, 3
2, 3, 4
3, 4, 1
1, 2, 4

11. 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.

one of the root's children
the larger child of the root
the smaller child of the root
the last node in the heap

12. 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.

the new root
the last node in the heap
the left child of the root
the right child of the root

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

yes
no
can't say
none of these

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

yes
no
can't say
none of these

15. The worst-time complexity for heap sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

16. The average-time complexity for heap sort is _________

O(logn)
O(n)
O(nlogn)
O(n*n)

17. The most efficient algorithm for sorting integer keys is __________.

quick sort
merge sort
heap sort