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