CS 2401 Test 3

Date: Thursday, April 30, 2009.
Name: ____________________________________________

1. Show, step by step, how bubble sort will sort a list 4, 3, 0, 2, 9. No code is needed. What is the worst-case and average complexity of bubble sort?



















































2. Show, step by step, how selection sort will sort a list 4, 3, 0, 2, 9. No code is needed. What is the worst-case and average complexity of selection sort?


























































3. Show, step by step, how insertion sort will sort a list 4, 3, 0, 2, 9. No code is needed. What is the worst-case and average complexity of insertion sort?

























































4. Show, step by step, how quicksort will sort a list 4, 3, 0, 2, 9. No code is needed. What is the worst-case and average complexity of quicksort?

























































5. Show, step by step, how mergesort will sort a list 4, 3, 0, 2, 9. No code is needed. What is the worst-case and average complexity of mergesort?

























































6. Show, step by step, what will happen if we add elements 4, 3, 0, 2, and 9 to the binary search tree; do not forget to balance at every step at which balancing is necessary. No code is needed.

























































7. What is logarithm? What is log2(64)?



























































8. Show, step by step, how linear search will look for an element 0 in the list 4, 3, 0, 2, 9. No code is needed. What is the worst-case and average complexity of linear search?
























































9. Show, step by step, how binary search will look for an element 0 in the sorted list 0, 2, 3, 4, 9. No code is needed. What is the worst-case and average complexity of binary sort?

























































10. Write a code for binary search; assume that the list is implemented as an array.