嵌入式linux实验报告-三种排序算法的在linux和arm上执行速度比较.doc

嵌入式linux设计实验报告项目概要名称：三种排序算法的在linux和arm上执行速度比较具体内容和实验要求：三种或三种以上排序算法在ARMLinux上执行速度的比较：例如可以随机产生1000个数，在排序过程开始前计下系统时间，结束后再计下系统时间，算出时间差即为算法执行时间，每种算法需要多重复几次取平均值。项目分工需求分析：共同完成概要设计和详细设计：（李春元）负责整个程序的框架设计和具体函数的实现即代码注释；调试和改进：（李红）代码调试，包括调试实例的设计，功能的扩展和补充；实现：（共同完成）从visualc+调试成功，移植到linux系统下的相关改进（库的变化等等），挂载到arm9上的过程，比较三种环境下运行时间的差异。项目需求分析由实验要求可知，首先是确定三种排序算法，这个容易解决，我们选择的是快速排序，冒泡排序，简单排序；接着是随机数的产生；然后是怎样计下系统时间，最后是怎样用系统时间来计算多次排序的平均值，这里又会涉及到数据类型的强制转换。所以要实现这些要求，包括的函数主要有：main函数，冒泡排序函数，简单排序函数，快速排序函数，排序时间计算函数。代码的框架和具体的实验代码（概要设计和详细设计）由李春元同学完成。概要设计包括系统整体软硬件流程图，各个功能子模块的划分和描述；产生随机数简单排序冒泡排序快速排序时间统计调试结果与改进方案工程框架/main主程序完成题目要求main/产生随即数randomnumberbeforesort=randomnumber/根据题目要求计算所需时间并比较cost1=./TimeCost(intbeforesort,intmode)cost2=.cost3=./运行时间计算doubleTimeCost(intbeforesort,intmode)记住系统时间Current0foriteration=1:N/N为排序算法多次执行的次数casemode=1sort1(intbeforesort)casemode=2sort2(intbeforesort)casemode=3sort3(intbeforesort)end记住系统时间Current1cost=(Current1-Current0)/N；returncost；/排序算法，任意找三种sort1(intbeforesort)/algorithm1sort2(intbeforesort)/algorithm2sort3(intbeforesort)/algorithm3代码完成第一步：测试随即数函数是否正确，随机数产生由函数srand(unsigned)time(NULL)实现，在这代码后添加显示函数printf("thousandrandomnumbersfrom0to2000nn")；for(i=0；i<N；)/*输出显示格式的设置,每行显示14个数，共1000个数*/for(j=0；j<13；j+)rj+i.key=rand()%2000；r1i.key=ri.key；printf("%-6d",rj+i.key)；printf("n")；i=i+13；以观察随机数是否正确，这里开始处理点小问题，因为本实验要用同一排序法对同一组数据进行排序，每次排序后要恢复原待排序的数组，所以定义了两个同样的数组类型recdtyperN+1,r1N+1，后者用于恢复时使用。首先每产生一个随机数放到r和rl中，开始忘了这点，并没有r1i.key=ri.key；这句，结果排序时间均为零（太小了）。第二步：分析各排序算法的时间复杂度，用于验证程序是否正确。简单排序：根据循环体计算其时间复杂度-n(n-1)/2O(n2)，移动次数和比较次数依具体待排数而定，空间复杂度O(1)，不稳定；冒泡排序：根据循环体计算其时间复杂度-n(n-1)/2O(n2)，移动次数和比较次数依具体待排数而定，空间复杂度O(1)，稳定；快速排序：根据循环体计算其时间复杂度-O(nlogn)，移动次数和比较次数依具体待排数而定，空间复杂度O(logn)，当待排序数有序时，退化为冒泡排序，不稳定；第三步：测试三种排序的正确性，单独验证其正确，放在一个单独的程序中验证，只是验证一次排序的移动次数和比较次数，以及排序的的稳定性，测试的数据换成只有十个比较简单的数（0到20），这里就体现出了为什么李春元同学为什么要用一个结构体来表示每个数据，结构体中既包含了关键字的大小，也包括了每个关键字的位置信息，便于判断排序算法是否稳定，但是实验中并没有体现这点，这是考虑到了这个可能。这部分比较简单，没出大问题。第四步：对计算运行时间的函数的验证和整个程序的验证是一起进行的，总要是通过看三种排序所花的平均时间的大小来判断程序是否正确。预计的是快速排序>（冒泡排序，简单排序）。后两者基本相同。第五步：为了更好的体现个排序算法的优劣，还加入了记录移动次数和比较次数的变量，当待排序数很多和排序次数很大时影响也会很大，所以要验证移动次数和比较次数，这个和第三步共同进行。第六步：在linux系统上运行时要注意两者的兼容性，开始时李春元同学用了c+的输出输入流来显示输出，这在linux的编译环境下是不支持的，最后都改成了c中的printf语句以及main函数返回值不能为void。还要注意的是文件的后缀是.c。在linux上实现后，挂载到arm上再通过终端显示。实验结果同1000个数经100次排序后的平均数据A）Window上运行结果：B）Linux上运行结果：运行时间（s）数据移动次数比较次数简单排序0.028049450500292605冒泡排序0.03004945050010838124快速排序0.019042276168218790C）（arm）终端上运行结果：运行时间（s）数据移动次数比较次数简单排序10.460049450500292605冒泡排序12.15004945050010838124快速排序7.330042276539218741存在的问题和改进的方法；程序中并没有涉及到判断排序是否是稳定的，这是需要改进的地方，这在前面也提到了，在设计结构体typedefstructkeytypekey；/*定义关键字类型*/elemtypedata；/*定义元素中其他数据项*/recdtype；/*定义元素结点类型*/想到了这点，但没有深入下去，其实到这里也算是做到了，只需在初始化时对data赋初始值，标记每个数据的位置，移动时整个节点一起移动，最后每个节点完整输出，看key相同但data值不同的节点相对位置是变化了，没变则是稳定的，反之不稳定。参考文献【1】数据结构（C语言版）严蔚敏吴伟明编著，清华大学出版社；【2】C语言程序设计谭浩强著清华大学出版社；【3】嵌入式设计及Linux驱动开发指南基于ARM9处理器孙天泽，袁文菊，张海峰，北京：电子工业出版社；【4】嵌入式linux应用开发详解孙琼等北京：人民邮电出版社；源代码#include<stdlib.h>#include<stdio.h>#include<time.h>constintN=1000；/*待排序的数据个数常量*/typedefintkeytype；/*关键字数据类型定义*/typedefintelemtype；/*元素节点其他数据项数据类型定义*/typedefstructkeytypekey；/*定义关键字类型*/elemtypedata；/*定义元素中其他数据项*/recdtype；/*定义元素结点类型*/typedefstructlongintcp；/*记录比较次数*/longintmv；/*记录移动次数*/cpmv；/*r为待排序列的数组*/*n为待排序列元素的个数*/*cm用于记录关键字的比较和移动次数*/voidsimplesort(recdtyper,intn,cpmv*cm)/*简单选择排序法:由小到大排列*/inti,j,k；recdtypet；for(i=0；i<n-1；i+)k=i；for(j=i+1；j<n；j+)if(rj.key<rk.key)k=j；cm->cp+；/*比较一次，比较次数加一*/if(k!=i)t=ri；ri=rk；rk=t；cm->mv+=3；/*交换次数加3*/intBubbleSort(recdtyper,intn,cpmv*cm)/*冒泡排序*/inti,j,count=0；intflag；for(i=1；i<=n-1；i+)flag=0；j=n；while(j>=i+1)if(rj.key<rj-1.key)/*rj与rj-1比较*/*rj与rj-1进行交换*/r0=rj；/*r0作为暂存器，实现交换*/rj=rj-1；rj-1=r0；flag=1；/*如果有记录交换发生，则置交换标志为1*/cm->mv+=3；/*关键字移动次数加3*/cm->cp+；/*执行if语句，比较次数加1*/j-；/*如果无记录交换发生，则退出循环*/count+；returncount；/*s为排序区间的起始点*/*t为排序区间的终止点*/voidQuickSort(recdtyper,ints,intt,cpmv*cm)/*快速排序*/intlow=s；inthigh=t；r0=rs；/*将基准记录移至r0中*/while(low<high)while(low<high&&r0.key<rhigh.key)high-；/*high指针向前搜索*/cm->cp+；/*循环执行一次，计较次数加1*/cm->cp+；/*最后一次比较，次数加1*/if(low<high)rlow=rhigh；/*将high所指向的记录后移*/cm->mv+；/*关键字移动次数加1*/low+；while(low<high&&rlow.key<=r0.key)low+；/*low指针向后搜索*/cm->cp+；/*循环执行一次，比较次数加1*/if(low!=high)cm->cp+；/*比较次数加1*/if(low<high)rhigh=rlow；/*将low所指向记录前移*/cm->mv+；high-；/*high指针继续向前搜索*/rlow=r0；/*low=high，将r0移动到它的终结位置*/cm->mv+；if(s<low)QuickSort(r,s,high-1,cm)；/*对rs到rhigh-1区间进行快速排序*/if(low<t)QuickSort(r,high+1,t,cm)；/*对rhigh+1到rt区间进行快速排序*/voidRestore(recdtyper,recdtyper1,intn)/*恢复原始数据,用于每次排序后*/inti；for(i=1；i<=n；i+)ri=r1i；floatTimeCost(recdtype*r,recdtype*r1,intN,cpmv*cm,intmode)intk=0；floatcost；/程序运行所需时间intKK=100；inti=mode；clock_tstart,finish；switch(i)case1:start=clock()；/开始时间/cout<<"以下进行插入排序:"<<endl；/cout<<endl；for(k=1；k<KK；k+)simplesort(r,N,cm)；Restore(r,r1,N)；finish=clock()；/cost=(float)(finish-start)/KK；break；case2:start=clock()；intcount；for(k=1；k<KK；k+)count=BubbleSort(r,N,cm)；Restore(r,r1,N)；finish=clock()；cost=(float)(finish-start)/KK；break；case3:start=clock()；for(k=1；k<KK；k+)QuickSort(r,1,N,cm)；Restore(r,r1,N)；finish=clock()；/终止时间cost=(float)(finish-start)/KK；/通过终止和起始时间计算得出运行所需时间，原始单位为秒break；default:printf("*")；returncost；intmain()inti,j；floatcost；printf("thousandrandomnumbersfrom0to2000nn")；for(i=0；i<N；)/*输出显示格式的设置,每行显示14个数，共1000个数*/for(j=0；j<13；j+)rj+i.key=rand()%2000；r1i.key=ri.key；printf("%-6d",rj+i.key)；printf("n")；i=i+13；cpmvcm3；cpmv*p；/*cmpv类型指针,中间变量,记录排序的比较次数移动次数的平均值*/srand(unsigned)time(NULL)；/*初始化随机发生器*/printf("thousandrandomnumbersfrom0to2000nn")；for(i=0；i<N；)/*输出显示格式的设置,每行显示14个数，共1000个数*/for(j=0；j<13；j+)rj+i.key=rand()%2000；r1i.key=ri.key；printf("%-6d",rj+i.key)；printf("n")；i=i+13；for(i=0；i<3；i+)cmi.cp=0；cmi.mv=0；