Tutorial Exercises Week 04

Exercise 1

Heaps

Trace the addition of the following keys in turn to a heap with maximum on top. Trace it with both the linked tree-based and array heap structures.

55, 45, 41, 75, 81, 79, 14, 55, 24, 86, 73, 35

Trace the deletion of the maximum element (86) from the heap.

Exercise 2

Naive Bubble Sort

1 void bubbleSort(int items[], int n) {
2    int i, j;
3        
4    for(i = n - 1; i > 0 ; i--) {
5        for(j = 1; j <= i; j++) {
6            if (items[j] <  items[j - 1]) {
7                swap(j,j-1,items);
8            }
9        }
10    }
11}

Random order:	3,2,4,8,1
Sorted order:	1,2,3,4,5
Reverse order:	5,4,3,2,1

1. Show how each of these arrays above change as they are sorted by the program above.
2. How many swaps are performed on the random, sorted, reverse ordered data sets shown above
3. How many comparisons are peformed on the random, sorted and reverse ordered data sets shown above. By comparison we mean comparing two data elements from the array - we are not including the loop counter comparisons.
4. With each line of code associate a cost and a formula expressing the number of times the C statement on that line will be executed when sorting n items in the worst case.
5. What is the asymptotic worst case time complexity of the algorithm implemented by this program.
6. What is the time complexity of the algorithm in the best case?
7. Modify the program to implement bubble sort with early exit. What is the asymptotic worst case time complexity now? What is the time complexity now in the best case?

Exercise 3

Insertion Sort

1 void insertionSort(int items[], int n) {
2    int i, j, key;
3 
4    for(i = 1; i <  n; i++){
5        key = items[i];
6        for(j=i; j > 0 ; j--){
7            if(key < items[j-1]){
8                items[j] = items[j-1]; //item shifts along to make room
9            } else {
10                 break;
11           }
12       }
13       items[j]=key;
14    }  
15}

1. Show how each of the arrays from the previous question (sorted, random, reverse), change as they are sorted by the program above. For each one count the number of comparisons and number of shifts.

2. With each line of code associate a cost and a formula expressing the number of times the C statement on that line will be executed when sorting n items in the worst case.
3. What is the asymptotic worst case time complexity of the algorithm implemented by this program.
4. What is the time complexity of the algorithm implemented by this program in the best case?

Exercise 4

1. Explain what stability means in the context of sorting
2. Suppose you have an implementation of a sorting algorithm that sorts strings and is case insensitive (for example 'a' and 'A' are considered to be equal). Explain what is wrong with the following argument:

   I ran the following input through the program

   AAAAA
   zzzzz
   abcde
   aaaaa
   

   and the output of the program was

   AAAAA
   aaaaa
   abcde
   zzzzz
   

   This means my sorting program is stable

Exercise 5

Sorting Linked Lists

Implement selection sort, given the following definition of a linked list

typedef struct node * link;
struct node{
    Item item;
    link next;
};

Is your implementation stable? Is the array-based implementation from lectures stable?