快速排序算法上机报告

Quicsort上机报告

03120115

肖俊青

第一题

1.题目要求

Thisprojectrequiresyoutoimplementanoptimizedversionofquicksort,and

comparetheperformancesofthefollowingcombinations:

(1)Cutoffvalues(边界值)from0to1000(between0and1000);

(2)Takepivottobethe1stelement,random,medianofrandomthree,andmedianofrandomfive.

The

(1)

(2)

(3)testsmustbedoneonthefollowingthreekindsofinputs:sortedinput;reverse-orderedinput;randominput.

Thesizeofinputcanbetakenfrom20000to100000.Theruntimesmustbeplottedwithrespecttothesizestoillustratethedifference.(figureoutusingexcel,matlabintheReport)

2.需求分析

题目要求测试在四种中值产生方式（1st.random.Medianofthree.randomoffive）和三种输入方式(Sorted.Reversed.Random)以及不同的输入数据量（2w~10w）的情况下Quicksort的运行时间。因为要处理的数据量比较多，因此考虑使用文本进行数据的传输。

思路：根据三种输入方式分别设计三个输入产生函数CreateSorted和CreateReverd,CreateRandom分别产生足够数量的随机数并写入到Sorted.txt和Reversed.txt，Random.txt中。再从相应的文本中读入输出，并进行Quicksort并计时并输出到result.txt中。其中的Quicksort中的Patition中应支持四种中值产生方式。

3.源代码分析

分析：源代码中共有5个子函数，其中前两个用于实现Qiucksort（能选择中值方式）后面3个用于产生输出文件。主函数从文件读入输入并存入缓冲区中，此时计时开始，对缓冲区中数据进行Quicksort，然后计时结束，然后将排序结果输入到result.txt中，并在屏幕上输出Quicksort所花费的时间。

4.实例测试

例子：中值产生方式为Medianofthree，输入方式为Reversed，size为8w

。

可以看到Reversed.txt中已经产生了80000

个逆序排列的数

Result.txt中产生已经被Quicksort排序好的80000

个数。说明算法是正确的。

从屏幕看以看到此次Quicksort花费了88毫秒。

5.实际编程中遇到的问题

产生随机数中srand（）的位置问题

要想使用rand（）产生每次不一样的随机数，比较靠谱的做法是用srand()将时间设为seed，因为每次时间不一样，所以产生的的随机数也都不一样。但是自己一开始将srand()写在了for循环中，发现产生的随机数都是同一个数，但是单步调试的时候产生的又是不同的数！真是一个古怪的问题。查阅资料发现srand()的原理是根据seed产生一个表，产生的随机数从表中顺序产生，这意味着如果seed一样，那么产生的随机数序列是一样的。当将srand()写在循环中时，因为time()的返回值已秒为单位，所seed都是一样的，每次都输出了产生的表中的第一个数，因此都是一样的。而单步调试中seed不一样，所以随机数不一样。

解决方法：将srand()置于循环开始前，这样循环就会从表中顺序输出不同的数。 Quicksort中的中值处理问题

书上的Quicksort是将最后一个数选为中值，并且j的循环只到了size-1，这样就相当于跳过了中值。一开始没有仔细领会这一点，导致排序顺序不对。

解决方法：i，j循环的时候跳过中值，不然可能导致中值提前交换，从未破坏算法。

文件操作问题

一开始用一个流打算同时实现读写操作，最后发生了数据冲突。

解决方法：使用两个流分别控制读写。

④栈溢出的问题

程序各项测试通过，开始统计数据时发现在Reversed，1st，>40000的情况下会出现莫名崩溃。单步调试发现提示栈溢出。这是以前没有遇到过的问题。查阅资料发现是因为每次调用函数都会将一些数据保存进堆栈，当Quicksort中的递归出现太多次的时候就会出现栈溢出的问题。

解决方法：VC6.0的默认堆栈大小为1MB，将其设置为3MB解决问题。

6.Quicksort

中的时间统计分析

分析：此表记录了各种情况下算法花费的时间。其中time的单位为毫秒（取的三次平均值），size

的单位为个。

分析：此表反应了输入为Sorted的情况下各中值产生方式的时间花费情况。可以看到1st

的时间最久，其他三种差不多。

分析：这两张表反应了Reversd的情况下各中值产生方式的时间花费（第一张表是四种一起，第二张表示后三种）。可以看到1st的时间花费在数量级上远超其他三种，

而其他三种的情况差不多。

分析：此表反应了输入为Random的情况下各中值产生方式的时间花费情况。可以看到1st

花费的时间是小于其他三种的。而其他三种差不多。

综合分析：random,medianoffive,medianofthree在条件相同的情况下时间花费是差不多的。其关系基本为medianoffive>=medianofthree<=random。而1st比较奇怪，在输入为Sorted和Reversed时它花费的时间最多，尤其是Reversed时的时间是在数量级上远超其他所有情况；而当输入为Random

时，它花费的时间是所有情况最少的。

极值情况如上表所示。

第二题

1.题目要求

ImplementHoare’salgorithmandcompareitwithouralgorithminthetextbook.(体会有重复数据情况下，算法之间的优劣)。

Theinputisalsotakenform20000and100000(between0and1000),andthetests

shouldbedoneontherandominput.Theruntimesmustbeplottedwithrespecttothesizes

toillustratethedifference.(figureoutusingexcel,matlabintheReport)

2.需求分析

题目要求实现Hoare的Partition算法，并且已经给出伪代码，输入为random，中值产生方式为最后一个数，只需将其实现即可。

3.源代码分析

分析：程序先产生size数量的随机数存入Radom.txt中，再从中读取数据进入Buff缓冲区，并进行Hoare的Qsort,并输出时间，并将排序好的数存入result.txt中。

4.实例测试

当输入数据的size为20000

时。可以看到：

时间为3ms

。

Random.txt中产生了20000

个随机数。

Result.txt中产生了20000个已经顺序排序的数。

说明算法正确运行了。

5.统计分析

从统计图表可以看出，当size比较大时（此时重复的数很多），Hoare的算法效率明显高于了Origin的算法。当size=100000时，两者相差近一倍。

第三题

1.题目要求

Implementquicksortalgorithmusingtailrecursionandcompareitwiththeoriginalquicksortalgorithm.

Theinputisalsotakenform20000and100000(between0and1000),andthetestsshouldbedoneontherandominput.Theruntimesmustbeplottedwithrespecttothesizestoillustratethedifference.(figureoutusingexcel,matlabintheReport)

2.需求分析

看将最基础的Quicksort改为尾递归实现即可。

3.源代码分析

分析：将此处改为尾递归即可，不再赘述。

4.实例测试

size=50000

进行测试

用了14ms

。

产生了随机数。

顺序排列了产生的数。

可以看到算法是正确工作的。

5.统计分析

分析：可以看到，使用尾递归的情况下算法的效率略好于原来的，但好得十分有限，原因是在原来的算法中编译器自动对递归进行了尾递归优化，导致两者时间相差无几。

本文来源：https://www.bwwdw.com/article/wtpi.html