Berkeley CS 61B Homework8

hw8比较简单，按作业要求里的步骤写出来就好。
mergeSort: 若key相等先enqueue前面的，stable.
quickSort: partition时若k1=k2, k1先被dequeue,因此先被enqueue到qSmall/qEqual/qLarge,因此k1还是在k2前面，最后append不改变顺序, stable.

挺简单的一次作业，自己蠢，写了俩bug调了半天，哎，不过也对两个sort理解更深刻吧

自己写了各个method的测试代码，供大家测试使用。

1.     System.out.println("/* Test makeQueueOfQueues */");
   
2.     LinkedQueue q1 = makeRandom(15);
   
3.     System.out.println("q1:" + q1.toString());
   
4.     LinkedQueue q2 = makeQueueOfQueues(q1);
   
5.     System.out.println("q1:" + q1.toString());
   
6.     System.out.println("q2:" + q2.toString());   
   
7.     System.out.println("\n");
   
8. 
   
9.     System.out.println("/* Test mergeSortedQueues */");
   
10.     LinkedQueue q3 = new LinkedQueue();
    
11.     q3.enqueue(new Integer(0));
    
12.     q3.enqueue(new Integer(2));
    
13.     q3.enqueue(new Integer(4));
    
14.     q3.enqueue(new Integer(6));
    
15.     q3.enqueue(new Integer(8));
    
16.     LinkedQueue q4 = new LinkedQueue();
    
17.     q4.enqueue(new Integer(1));
    
18.     q4.enqueue(new Integer(3));
    
19.     q4.enqueue(new Integer(5));
    
20.     q4.enqueue(new Integer(7));
    
21.     q4.enqueue(new Integer(9));
    
22.     q4.enqueue(new Integer(11));
    
23.     q4.enqueue(new Integer(13));
    
24.     q4.enqueue(new Integer(15));
    
25.     System.out.println("q3:" + q3.toString());
    
26.     System.out.println("q4:" + q4.toString());
    
27. 
    
28.     LinkedQueue q5 = mergeSortedQueues(q3, q4);
    
29.     System.out.println("q3:" + q3.toString());
    
30.     System.out.println("q4:" + q4.toString());
    
31.     System.out.println("q5:" + q5.toString());
    
32.     System.out.println("\n");
    
33. 
    
34.     System.out.println("/* Test mergeSort */");
    
35.     LinkedQueue q = makeRandom(25);
    
36.     System.out.println("q: " + q.toString());
    
37.     mergeSort(q);
    
38.     System.out.println("q: " + q.toString());
    
39.     System.out.println("\n");
    
40. 
    
41.     System.out.println("/* Test partition */");
    
42.     LinkedQueue q6 = makeRandom(20);
    
43.     System.out.println("q6:" + q6.toString());
    
44.     LinkedQueue q6Small = new LinkedQueue();
    
45.     LinkedQueue q6Equals = new LinkedQueue();
    
46.     LinkedQueue q6Large = new LinkedQueue();
    
47.     int pivotNum = ThreadLocalRandom.current().nextInt(1, q6.size() + 1);
    
48.     Comparable pivot = (Comparable) q6.nth(pivotNum);
    
49.     System.out.println("pivot is: " + pivot);
    
50.     partition(q6, pivot, q6Small, q6Equals, q6Large);
    
51. 
    
52.     System.out.println("q6:" + q6.toString());
    
53.     System.out.println("q6Small:" + q6Small.toString());
    
54.     System.out.println("q6Equals:" + q6Equals.toString());
    
55.     System.out.println("q6Large:" + q6Large.toString());
    
56.     System.out.println("\n");
    
57. 
    
58.     System.out.println("/* Test quickSort */");
    
59.     q = makeRandom(100);
    
60.     System.out.println(q.toString());
    
61.     quickSort(q);
    
62.     System.out.println(q.toString());
    
63.     System.out.println("\n");
    
64. 
    
65.     /* Remove these comments for Part III. */
    
66.     System.out.println("/* Test Part III */");
    
67.     Timer stopWatch = new Timer();
    
68.     q = makeRandom(SORTSIZE);
    
69.     stopWatch.start();
    
70.     mergeSort(q);
    
71.     stopWatch.stop();
    
72.     System.out.println("Mergesort time, " + SORTSIZE + " Integers:  " +
    
73.                        stopWatch.elapsed() + " msec.");
    
74. 
    
75.     stopWatch.reset();
    
76.     q = makeRandom(SORTSIZE);
    
77.     stopWatch.start();
    
78.     quickSort(q);
    
79.     stopWatch.stop();
    
80.     System.out.println("Quicksort time, " + SORTSIZE + " Integers:  " +
    
81.                        stopWatch.elapsed() + " msec.");
    
82.     System.out.println("\n");
    
83. 
    
84.     System.out.println("/* Test Part IV */");
    
85.     LinkedQueue q7 = new LinkedQueue();
    
86.     Entry e1 = new Entry(new Integer(3), "spa");
    
87.     Entry e2 = new Entry(new Integer(7), "hex");
    
88.     Entry e3 = new Entry(new Integer(3), "boo");
    
89.     Entry e4 = new Entry(new Integer(7), "for");
    
90.     q7.enqueue(e1);
    
91.     q7.enqueue(e2);
    
92.     q7.enqueue(e3);
    
93.     q7.enqueue(e4);
    
94. 
    
95.     System.out.println("\t\t q7: " + q7);
    
96.     mergeSort(q7);
    
97.     System.out.println("After mergeSort, q7: " + q7);
    
98.     System.out.println("\n");
    
99. 
    
100.     LinkedQueue q8 = new LinkedQueue();
     
101.     q8.enqueue(e1);
     
102.     q8.enqueue(e2);
     
103.     q8.enqueue(e3);
     
104.     q8.enqueue(e4);
     
105. 
     
106.     System.out.println("\t\t q8: " + q8);
     
107.     quickSort(q8);
     
108.     System.out.println("After quickSort, q8: " + q8);

复制代码

最后的 Part IV 用到了之前作业的Entry.java。方便debug，加上了 toString() 和 compareTo()。

1. /* Entry.java */
   
2. 
   
3. /**
   
4. *  A class for dictionary entries.
   
5. **/
   
6. 
   
7. public class Entry implements Comparable <Entry> {
   
8. 
   
9.   protected Object key;
   
10.   protected Object value;
    
11.   
    
12.   public Entry (Object k, Object v) {
    
13.     key = k;
    
14.     value = v;
    
15.   }
    
16. 
    
17.   public Object key() {
    
18.     return key;
    
19.   }
    
20. 
    
21.   public Object value() {
    
22.     return value;
    
23.   }
    
24. 
    
25.   //Add toString for testing
    
26.   public String toString() {
    
27.     return "[" + key + ", " + value + "]";
    
28.   }
    
29. 
    
30.   public int compareTo(Entry e) {
    
31.     Comparable thisComp = (Comparable) key;
    
32.     Comparable eComp = (Comparable) e.key;
    
33.     if (thisComp.compareTo(eComp) < 0) {return -1;}
    
34.     else if (thisComp.compareTo(eComp) == 0) {return 0;}
    
35.     else {return 1;}
    
36.   }
    
37. 
    
38. }
    

复制代码

Part III and Part IV

1. Part III.  Running time comparisons
   
2. 
   
3.   List size         mergesort             quicksort
   
4.       100              1 ms                 0 ms
   
5.     1,000              2 ms                 1 ms
   
6.    10,000              8 ms                 9 ms
   
7.   100,000            200 ms               121 ms
   
8. 1,000,000           2308 ms              1442 ms
   
9. 
   
10. Part IV.
    
11. 
    
12.   Is mergesort stable?  
    
13.   Why or why not?
    
14.   Yes. Because when there are two keys are equal, the key from q1 (left)
    
15.   will be enqueued, which comes from the left. In this case, the order is
    
16.   remained. However, if the key from q2 (right) will be enqueued, then the
    
17.   order cannot be remained.
    
18. 
    
19.   Is quicksort stable?  
    
20.   Why or why not?
    
21.   Yes. Because all equal keys are preserved in qEquals queue and they are
    
22.   enqueued in the order which they have in the original queue. Therefore,
    
23.   the order are retained.

复制代码

这次作业挺简单的哈哈~老师的测试时间的代码还没看，先交作业！

第八次作业

俘虏你的心 发表于 2017-3-9 15:20
自己写了各个method的测试代码，供大家测试使用。

受到这位同学的启发，我对test code中part IV进行了一个小改动（增加一个entry，使LinkedQueue中的item数量为奇数）

1. System.out.println("/* Test Part IV */");
   
2.     LinkedQueue q7 = new LinkedQueue();
   
3.     Entry e1 = new Entry(new Integer(3), "spa");
   
4.     Entry e2 = new Entry(new Integer(7), "hex");
   
5.     Entry e3 = new Entry(new Integer(3), "boo");
   
6.     Entry e4 = new Entry(new Integer(7), "for");
   
7.     // add one more item, so that total number is odd.
   
8.     Entry e5 = new Entry(new Integer(3), "mee");
   
9.     q7.enqueue(e1);
   
10.     q7.enqueue(e2);
    
11.     q7.enqueue(e3);
    
12.     q7.enqueue(e4);
    
13.     q7.enqueue(e5);
    
14. 
    
15.     System.out.println("\t\t q7: " + q7);
    
16.     mergeSort(q7);
    
17.     System.out.println("After mergeSort, q7: " + q7);
    
18.     System.out.println("\n");
    
19. 
    
20.     LinkedQueue q8 = new LinkedQueue();
    
21.     q8.enqueue(e1);
    
22.     q8.enqueue(e2);
    
23.     q8.enqueue(e3);
    
24.     q8.enqueue(e4);
    
25.     q8.enqueue(e5);
    
26. 
    
27.     System.out.println("\t\t q8: " + q8);
    
28.     quickSort(q8);
    
29.     System.out.println("After quickSort, q8: " + q8);

复制代码

然后运行就可以发现：当q1.key == q2.key时，如果mergesort中先加入q1.key，再加入q2.key的话，那么这样实现的mergesort是unstable.

求学分，时间这么长，不明白是自己太垃圾了还是电脑太垃圾了....

交作业。作业里mergesort的实现思路和G&T里的Nonrecursive Array-Based Implementation of Merge-Sort的思想是一样的，巩固了一下。

我的mergeSort stable的，因为我的 merge方法，在item1<=item2时，都q1.deque（如果item<item2,q1.deque,就不stable了），所以整个顺序不变。
quickSort 也是stable的，因为整个qEqual的 item里面没有没移动过。


求加学分！！！另外之前的学分也没加！！

恩，不该浪费这么长时间的其实，只是我忘记了void method把q给empty了之后，可以用append()给结果加回来，结果研究了半天形参和reference、object，还有函数间传递等等等等，也不算全无收获吧，就当复习基本概念了（虽然我一开始的概念就是对的，只是蠢了而已……）另外这次作业蛮简单的，因为每一步的提示都太到位了，每一个方法如何实现，算法老师都给写出来了，说实话感觉更像是一次lab吧。至于stable的问题，我的结论和楼上老哥一样~