Berkeley CS 61B Homework8

还有两次作业~~~~

run:
[ 4 6 7 4 8 0 5 0 5 1 ]
[ 0 0 1 4 4 5 5 6 7 8 ]
[ 1 2 3 5 6 7 5 4 8 8 ]
[ 1 2 3 4 5 5 6 7 8 8 ]
Mergesort time, 1000 Integers:  0 msec.
Quicksort time, 1000 Integers:  16 msec.
成功构建 (总时间: 40 秒)

run:
[ 1 3 5 4 8 9 1 0 7 2 ]
[ 0 1 1 2 3 4 5 7 8 9 ]
[ 2 1 3 7 1 8 9 6 0 1 ]
[ 0 1 1 1 2 3 6 7 8 9 ]
Mergesort time, 10000 Integers:  32 msec.
Quicksort time, 10000 Integers:  46 msec.
成功构建 (总时间: 8 秒)

run:
[ 5 0 5 6 6 9 8 4 9 9 ]
[ 0 4 5 5 6 6 8 9 9 9 ]
[ 9 7 0 8 4 7 9 4 2 7 ]
[ 0 2 4 4 7 7 7 8 9 9 ]
Mergesort time, 100000 Integers:  546 msec.
Quicksort time, 100000 Integers:  546 msec.
成功构建 (总时间: 41 秒)

run:
[ 8 2 7 9 2 8 2 6 3 4 ]
[ 2 2 2 3 4 6 7 8 8 9 ]
[ 0 2 6 9 6 5 3 1 3 3 ]
[ 0 1 2 3 3 3 5 6 6 9 ]
Mergesort time, 1000000 Integers:  17473 msec.
Quicksort time, 1000000 Integers:  9968 msec.
成功构建 (总时间: 57 秒)


无解了。。我的电脑

就没看到比我慢的

在我的算法中，归并排序的merge函数在q1 q2 元素相等时每次优先将q1的元素放入新队列中，因此顺序可能会改变，所以不是stable；
快速排序中，由于有了qEquals队列的存在，相等的元素顺序并不会改变，因此是stable的。

通过这次作业对quick sort和recursion有了更深的理解，感觉recursion理解的还不是很透彻。
MergeSort 是不stable的， 在我的MergeSortedQUeue中，如果两个item 相等，先enqueue q1中的，这样就打乱了出现的顺序。
QuickSort 是stable的，equal的item 还是按照原来的顺序出现。

Mergesort :
[ 8 8 4 7 3 8 7 8 9 1 ]
[ 1 3 4 7 7 8 8 8 8 9 ]
Quicksort:
[ 1 3 7 3 5 2 4 5 8 2 ]
[ 1 2 2 3 3 4 5 5 7 8 ]
Mergesort time, 10 Integers:  0 msec.
Quicksort time, 10 Integers:  0 msec.
➜  hw8  javac -g ListSorts.java
Note: ListSorts.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
➜  hw8  java ListSorts
Mergesort :
[ 2 3 9 8 2 6 1 3 3 6 ]
[ 1 2 2 3 3 3 6 6 8 9 ]
Quicksort:
[ 3 5 9 2 7 3 8 7 0 6 ]
[ 0 2 3 3 5 6 7 7 8 9 ]
Mergesort time, 100 Integers:  1 msec.
Quicksort time, 100 Integers:  0 sec.

➜  hw8  java ListSorts
Mergesort :
[ 4 5 0 6 3 8 7 2 4 3 ]
[ 0 2 3 3 4 4 5 6 7 8 ]
Quicksort:
[ 5 3 4 9 8 3 9 7 0 0 ]
[ 0 0 3 3 4 5 7 8 9 9 ]
Mergesort time, 1000 Integers:  6 msec.
Quicksort time, 1000 Integers:  3 sec.

➜  hw8  java ListSorts
Mergesort :
[ 5 3 3 6 6 1 9 4 9 9 ]
[ 1 3 3 4 5 6 6 9 9 9 ]
Quicksort:
[ 2 7 7 7 7 9 8 9 7 6 ]
[ 2 6 7 7 7 7 7 8 9 9 ]
Mergesort time, 10000 Integers:  17 msec.
Quicksort time, 10000 Integers:  19 msec.

这次作业不难，但是因为细节上的问题还是debug了挺久

确实不难，上图

这么一比，我台式机还挺快的哈

quick sort, the "big daddy" lol

出去浪了几天.....继续...