Tutorial Solutions Week 04
Exercise 1
HeapsTrace 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.
array version
The first element at index 0 is not used in our implementation.
55
55
/
45
55
/ \
45 41
55 55 75
/ \ / \ / \
45 41 => 75 41 => 55 41
/ / /
75 45 45
75 75 81
/ \ / \ / \
55 41 => 81 41 => 75 41
/ \ / \ / \
45 81 45 55 45 55
81 81
/ \ / \
75 41 => 75 79
/ \ / / \ /
45 55 79 45 55 41
81
/ \
75 79
/ \ / \
45 55 41 14
81 81
/ \ / \
75 79 75 79
/ \ / \ / \ / \
45 55 41 14 => 55 55 41 14
/ /
55 45
81
/ \
75 79
/ \ / \
55 55 41 14
/ \
45 24
81 81
/ \ / \
75 79 75 79
/ \ / \ / \ / \
55 55 41 14 => 55 86 41 14 =>
/ \ / / \ /
45 24 86 45 24 55
81 86
/ \ / \
86 79 81 79
/ \ / \ / \ / \
55 75 41 14 => 55 75 41 14
/ \ / / \ /
45 24 55 45 24 55
86
/ \
/ \
/ \
81 79
/ \ / \
55 75 41 14
/ \ / \ /
45 24 55 73 35
x 55
x 55 45
x 55 45 41
x 75 55 41 45
x 81 75 41 45 55
x 81 75 79 45 55 41
x 81 75 79 45 55 41 14
x 81 75 79 55 55 41 14 45
x 81 75 79 55 55 41 14 45 24
x 86 81 79 55 75 41 14 45 24 55
x 86 81 79 55 75 41 14 45 24 55 73
x 86 81 79 55 75 41 14 45 24 55 73 35
Removing the minimum
35 81
/ \ / \
81 79 35 79
/ \ / \ / \ / \
55 75 41 14 => 55 75 41 14
/ \ / \ / \ / \
45 24 55 73 45 24 55 73
81 81
/ \ / \
75 79 75 79
/ \ / \ / \ / \
55 35 41 14 => 55 73 41 14
/ \ / \ / \ / \
45 24 55 73 45 24 55 35
Array version
x 81 75 79 55 73 41 14 45 24 55 35
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 |
- Show how each of these arrays above change as they are sorted by the
program
above.
Showing array at the start and then after each swap Random Order 3 2 4 8 1 2 3 4 8 1 2 3 4 1 8 2 3 1 4 8 2 1 3 4 8 1 2 3 4 8 Sorted Order 1 2 3 4 5 Reverse Ordered 5 4 3 2 1 4 5 3 2 1 4 3 5 2 1 4 3 2 5 1 4 3 2 1 5 3 4 2 1 5 3 2 4 1 5 3 2 1 4 5 2 3 1 4 5 2 1 3 4 5 1 2 3 4 5
- How many swaps are performed on the random, sorted, reverse ordered data sets shown above
random : 5
sorted : 0
reverse :10
- 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. 10 comparisons no matter what for data of size 5
- 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.
Solution
Line
Cost
Times
4
c0
n
5
c1
n + (n-1) + ... + 1 = (n (n+1)) /2
6
c2
(n-1) + (n-2) + ... + 1 = (n (n-1)) /2
7
c3
(n-1) + (n-2) + ... + 1 = (n (n-1)) /2
Because in the worst case the comparison is always true so we always swap- What is the asymptotic worst case time complexity of the algorithm implemented by this program. O(n^2)
- What is the time complexity of the algorithm in the best case? We never have to swap or execute line 7 but it is still O(n^2)
- 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?
1 void bubbleSortEE(int items[], int n) { 2 int i, j; 3 int done = 0; //added this line 4 for(i = n - 1; i > 0 && !done ; i--) { //updated this line done = 1; //added this line 5 for(j = 1; j <= i; j++) { 6 if (items[j] < items[j - 1]) { 7 swap(j,j-1,items); 8 done = 0; //added this line } 9 } 10 } 11}Now in the best case when the data is already in sorted order, inner loop only needs to go through once. No swaps are done and then the outer loop finishes. This makes it O(n) in the best case. In the worst case and overall we still say it is an O(n^2) algorithm.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}- 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.
Sorted: 4 comparisons and 0 shifts 1 2 3 4 5 Random: 7 comparisons and 5 shifts 3 2 4 8 1 At the end of each outer for loop 2 3 4 8 1 2 3 4 8 1 2 3 4 8 1 1 2 3 4 8 Reverse: 10 comparisons and 10 shifts 5 4 3 2 1 At the end of each outer for loop 4 5 3 2 1 3 4 5 2 1 2 3 4 5 1 1 2 3 4 5
- 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.
Solution
Line
Cost
Times
4
c0
n
5
c1
n - 1
6
c2
2 + 3 + ... + n = (n (n+1)) /2 - 1
7
c3
1 + 2 + ... + (n-1) = (n (n-1)) /2
8
c4
1 + 2 + ... + (n-1) = (n (n-1)) /2
10
c5
0
7
c6
n-1
- What is the asymptotic worst case time complexity of the algorithm implemented by this program. O(n^2)
- What is the time complexity of the algorithm implemented by this program in the best case? We always break out of the inner loop after the first comparison, so we only execute lines 6 and 7 n -1 times. We never execute line 8 and we execute line 10 n -1 times. So over all we have a time complexity of O(n) for the best case. We still classify this algorithm as O(n^2) overall as that is its worst case complexity.
Exercise 4
- Explain what stability means in the context of sorting
A stable sorting algorithm preserves the order of duplicates. An un-stable sorting
algorithm does not always preserve the order of duplicates. For example if you had a sorting
algorithm that was case insensitive and sorted the following input.
zzzz AAAA csdf aaaa
and the output wasaaaa AAAA csdf zzzz
Then the order of the duplicates "AAAA" and "aaaa" has changed after the data has been sorted. This would prove that the algorithm was unstable as we have found a counter example where stability is not preserved. - 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 wasAAAAA 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; };link selectionSort(link list){ link sorted = NULL; link curr = NULL; link prev = NULL; link max = NULL; link maxPrev = NULL; // Keep finding the max in the original list // and adding to the front of the sorted list // until the original list is empty while(list != NULL){ //Find max prev = NULL; maxPrev = NULL; max = list; for(curr = list ;curr!=NULL;curr= curr->next){ if(curr->item > max->item){ max = curr; maxPrev = prev; } prev = curr; } //Remove from original list if(maxPrev != NULL){ maxPrev->next = max->next; }else{ list = max->next; } // Add the max to the front of the sorted list max->next = sorted; sorted = max; } return sorted; }This implementation is not stable. An example of why not is that if there were duplicates, the first copy would be put a the front, then the next copy would be put at the front thus reversing the order of duplciates. By changing the code to have >= instead of > when looking for the max it would be.
if(curr->item >= max->item){ max = curr; maxPrev = prev; }The implementation of selection sort using arrays from lectures is not stable as when the max/min item is selected it is swapped with the item at the appropriate location. When this swap occurs, the item that was at the appropriate location could be swapped to a position that makes it come after any of its duplicates.
Even if we were sorting something simple like 1 1 2 in descending order it would end up reversing the 1s.
This would be harder to make stable without having to shift possibly many items in the array and making the implementation less efficient.