Berkeley CS 61B Homework8

一开始在mergeSortedQueues()中想到的是用nth()方法通过count i和j来对比q1和q2中值的大小，也能做出来。后面开始计时之后发现这个方法特别慢，因为每调用一次nth(n)方法，他都要进行n次循环，大大增加了计算次数。后来就干脆用front()得到的值进行对比,再用dequeue()和enqueue()方法。Linkedlist有remove first node的操作，但如果是Array的话就要用到count了。

确实挺简单的但是写mergesort的时候考虑2个LinkedQueue长度不一样情况脑抽纠结了蛮久。

1. [ 6 0 7 2 3 3 8 9 0 7 ]
   
2. [ 0 0 2 3 3 6 7 7 8 9 ]
   
3. [ 2 8 7 0 4 9 6 9 1 7 ]
   
4. [ 0 1 2 4 6 7 7 8 9 9 ]
   
5. --- test the list of size zero ---
   
6. [ ]
   
7. [ ]
   
8. [ ]
   
9. --- test the list of size one ---
   
10. [ 1 ]
    
11. [ 1 ]
    
12. [ 1 ]
    
13. Mergesort time, 1000000 Integers:  3639 msec.
    
14. Quicksort time, 1000000 Integers:  1233 msec.
    

复制代码

这个作业比较简单，相对hw7来说。。。 2-3-4 tree写着好烦，还不如去写red-black-tree。
用queue写对于list的merge sort挺有意思的。。

我们都知道array based merge sort是stable的，
但是这里
input size是偶数，就是stable，因为两个queue的相对位置会永远保持一致。
input size是奇数，那就不能保证stable。

当然，input size偶数，stable的前提是，merge都时候，遇到相同情况，要选优先选择，首先dequeue出来的那一侧的queue。
有些人在相同的情况下，随机选，那当然就不能保证stable。

交作业，听大家说比较简单实际上还是写了很久，写mergeSort()的时候考虑了很多种情况，包括引用为null及size为0，最后debug出现了一个意外：
我在mergeSort()函数中使用了try{}catch{}，在try最后我开始用 p = xxx.deque() （其中xxx为queueOfQueues）来获取排序后的q，这时该函数内q是有引用的，但是到了主函数q的输出就是[ ]了，引用也没了，后来我改成了p.append()来获取排序后的q，这样就正确了，想问大家知道这个的原理么？

MergeSort not stable ,5 6 6 7和1 6 8 merge时，6的顺序会被打乱
QuickSort stable


补充内容 (2018-6-15 23:13):
还有一个导致not stable的原因：当size()为奇数，最后一个剩下的queue在下一轮merge时顺序会打乱

SwaggyXuan 发表于 2018-6-11 16:28
交作业，听大家说比较简单实际上还是写了很久，写mergeSort()的时候考虑了很多种情况，包括引用为null及s ...

我认为即使mergesort是偶数也不是stable
比如 3(A) 3(B) 1(C) 3(D)进行排序，排出的结果应该为 [3(A) 3(B)]  [1(C) 3(D)]   then  [1(C)  3(A)  3(D)  3(B)]

交作业，写quicksort的时候想了挺久，感觉还是对递归不太理解。

Is your mergesort always stable?  Explain why or why not.
  No, because when you merge two items and enqueue it back to the queue, the order of items with the same key might have changed. An example: 3’ 4 5 3’’ 2, after mergesort: 2 3’’ 3’ 4 5

Is your quicksort always stable?  Explain why or why not.
  Yes, because the order of items with the same key is preserved in qEqual.

本次作业整体还是比较简单的，（不过我还是参考了一下别人的clean code）大概是因为这个quicksort不是老师最后讲的基于array的in-place的quick-sort吧。
要注意的地方就是
1.注意捕捉异常
2.dequeue一个比较item的时候要强制转换成 Comparable
3.产生一个1到size的随机数 我参考了别人的方法:int index=((int)(Math.random()*100000))%q.size()+1; 注意因为random()返回的是double，因此我们需要强制转型
4.感觉老师上课讲的真的超级好，之前merge sort和quick sort怎么听怎么就有地方不太理解，听了老师的课才发现不同的数据结构会对算法造成影响！怪不得我总是看到不同版本的排序算法！