Problem Set 13 – Solution Sorting
1. Trace the mergesort algorithm on the following list:
3, 26, 67, 25, 9, -6, 43, 82, 10, 54
Show the resulting recursion tree, with the to-be-sorted original and sub-lists at each node, and the number comparions for each merge. (Assume that if there is an odd number of entries in an array, the left part has one more entry than the right after the split.)
SOLUTION
The original and sorted result indicated above and below:
-6,3,9,10,25,24,43,54,67,84 #c9
3, 26, 67, 25, 9, -6, 43, 82, 10, 54 /\
/\
/ 3,9,25,26,67 #c3 \ -6,10,43,54,82 #c4
3, 26, 67, 25, 9 -6, 43, 82, 10, 54 /\/\ /\/\
/ 3,26,67 #c2 \ 9,25 #c1 / -6,43,82 #c2 \ 10,54 #c1 3, 26, 67 25, 9 -6, 43, 82 10, 54
/\/\/\/\ /3,26 #c1 \ 67 / 9 \ 25 /-6,43 #c1 \ 82 / 10 \ 54
3,26 67925-6,43 821054
/\ /\ /3 \6 /-6\43
3 26 -6 43
2. Mergesort works well on linked lists since it doesn’t need any extra space. Given the following linked list node class:
public class LLNode
public LLNode
…
}
complete the following method to “split” the linked list in half:
// splits the given list in half such that the return value is
// a reference to the first node of the second half. Also, the
// “next” field of the last node in the first half is set to null. static
// COMPLETE THIS METHOD }
SOLUTION
static
int size=0; LLNode
for (ptr=list; ptr
size++; }
size = (size+1)/2; while (size > 1) { ptr = ptr.next;
size–; }
LLNode
!= null; ptr = ptr.next) { ptr=list;
ptr.next;
}
3. In Problem Set 3, #6, you saw how to merge two sorted linked lists of integers, into a single sorted list without duplicates. Here is the header of a modified version of that method, that merges lists of Comparable objects
(not just ints), while preserving duplicates, if any. Complete this method using recursion. Your method should recycle the nodes in the original lists (no new nodes should be created).
// merge the lists l1 and l2 into a single linked list, whose
// first node is referenced by the return value – no additional
// linked list nodes are used
static
// COMPLETE METHOD USING RECURSION, NO NEW NODES TO BE CREATED }
Using this merge solution, and the solution to the split in the previous problem, complete the mergesort implementation:
// Sorts the input linked list using mergesort, and returns the front of // the sorted linked list. DOES NOT CREATE ANY ADDITIONAL NODES.
public static
LLNode
// COMPLETE THIS METHOD }
SOLUTION
// merge the lists l1 and l2 into a single linked list, whose
// first node is referenced by the return value – no additional
// linked list nodes are used
static
// COMPLETE METHOD USING RECURSION, NO NEW NODES TO BE CREATED if (l1 == null) { return l2; }
if (l2 == null) { return l1; }
if (l1.info.compareTo(l2.info) < 0) {
l1.next = merge(l1.next, l2);
return l1; } else {
l2.next = merge(l1, l2.next);
return l2; }
}
public static
if (list == null || list.next == null) {
return list; }
// split
LLNode
// recursive calls
list = mergesort(list); second = mergesort(second);
// merge
return merge(first, second); }
4. Trace the quicksort algorithm on the following array:
3, 26, 67, 25, 9, -6, 43, 82, 10, 54
Use the median of the first, middle, and last entries as the pivot to split a subarray. (If a subarray has fewer than 3 entries, use the first as the pivot.) Show the quicksort tree and the number of comparisons at each split.
SOLUTION
[3 26 67 25 9 -6 43 82 10 54] median(3,9,54)=9, swap(9,3) split
| pivot=9, # of comp = 9
V [3 -6] 9
[25 67 26 43 82 10 54] split
| piv=43,#c = 6
split
| piv=3,#c = 1 VV
[-6]3 [251026] 43 [826754] split split
Total number of comparisons = 20
| piv=25,#c=2 | piv=67,#c=2
VV
[10] 25 [26] [54] 67 [82]
5. A stable sorting algorithm is one which preserves the order of duplicate elements when sorted. For instance, if the following (key,value) pairs are sorted on the keys: (3,sun) (2,mars) (4,moon) (3,venus)
then the output of a stable sorting algorithm would be:
(2,mars) (3,sun) (3,venus) (4,moon)
Notice that (3,sun) comes before (3,venus), preserving the order of the input for elements that have the same key (i.e. 3), hence stable. However, if the output is this:
(2,mars) (3,venus) (3,sun) (4,moon)
then the sorting algorithm is not stable since it does not preserve the input order of (3,sun) before (3,venus). For each of insertion sort, mergesort, and quicksort, tell whether the algorithm is stable or not.
SOLUTION
Insertion sort is a stable sort. Mergesort is a stable sort. Quicksort is not a stable sort.
6. Given the following input array:
3, 26, 67, 25, 9, -6, 43, 82, 10, 54
1. Trace the linear time build-heap algorithm on this array, to build a max-heap. How many comparisons did it take to build the heap?
2. Starting with this max-heap, show how the array is then sorted by repeatedly moving the maximum entry to the end and applying sift-down to restore the (remaining) heap. How many comparisons did it take to sort the
heap?
SOLUTION
1.
2.
Sift Down Comparisons ——— ———–
91 25 2 67 2 26 4
3 5 done
Array ——————————————— 32667259-643821054
326672554-64382109 326678254-64325109 326678254-64325109 382672654-64325109 825467269-64325103
Array ——————————————— 82 54 67 26 9 -6 43 25 10 3
swap(82,3) 35467269-643251082
67 54 43 26 9 -6 3 25 10 82 swap(67,10)
105443269-63256782
54 26 43 25 9 -6 3 10 67 82 swap(54,10)
102643259-63546782
43 26 10 25 9 -6 3 54 67 82 swap(43,3)
32610259-643546782
26 25 10 3 9 -6 43 54 67 82 swap(26,-6)
-62510392643546782
25 9 10 3 -6 26 43 54 67 82 swap(25,-6)
-69103252643546782
Sift Down
——— ———–
10 9 -6 3 25 26 swap(10,3)
3 9 -6 10 25 26
9 3 -6 10 25 26 swap(9,-6)
-6 3 9 10 25 26
3 -6 9 10 25 26 swap(3,-6)
43 54 67 82 43546782
43 54 67 82 43546782
43 54 67 82
10 6
10 4
3 4
-6 4
-6 2
3 2
-6 1
Comparisons 3 4
-6 3 9 10 25 26 43 54 67 82 done