实现快排最优版本算法上机报告

1、算法导论第二次上机报告班级：1403018 姓名：张可心 学号一）题目一一、问题This project requires you to implement an optimized version of quicksort, and compare the performances of the following combinations:(1) Cutoff values from 0 to 50;(2) Take pivot to be the 1st element, random, median of random three, and median of

2、 random five.The tests must be done on the following three kinds of inputs:(1) sorted input;(2) reverse-ordered input;(3) random input.The size of input can be taken from 1000 to 10000. The run times must be plotted with respect to the sizes to illustrate the difference. (figure out using excel, mat

3、lab in the Report)二、问题分析实现快排的最优版本，分别选取第一个数，随机数，三个随机数的中位数，五个随机数的中位数为基数，设置顺序，随机，逆序三种形式，用_qsort(int a,int p,int r,int number)和Partition(int a,int p,int r,int number)俩函数进行排序。三、算法伪代码void _qsort(a, p, r, number)if p<r q=Partition(a,p,r,number)_qsort(a,p,q-1,number)_qsort(a,q+1,r,number)int Partition(in

4、t a,int p,int r,int number)int x,temp;if(number=1) temp=p;else if(number=2) temp=rand()%(r-p+1)+p;else if(number=3)int b5;b1=rand()%(r-p+1)+p;b2=rand()%(r-p+1)+p;b3=rand()%(r-p+1)+p;sort(b+1,b+4);temp=b2; else if(number=4)int b10;b1=rand()%(r-p+1)+p;b2=rand()%(r-p+1)+p;b3=rand()%(r-p+1)+p;b4=rand()%

5、(r-p+1)+p;b5=rand()%(r-p+1)+p;sort(b+1,b+6);temp=b3;elsetemp=p;x=atemp;swap(atemp,ap);int i=r+1;for(int j=r;j>p;j-)if(aj>=x)i-;swap(ai,aj); swap(ai-1,ap);return i-1;int main() int n,a200000; cout<<"测试数据："cin>>n;for(int i=1;i<=n;i+) ai=random(51); cout<<"序列的顺

6、序（1顺序；2随机；3逆序）："int s;cin>>s;if(s=3) sort(a+1,a+1+n,greater<int>();/对生成数进行排列 else if(s=1) sort(a+1,a+1+n); else if(s=2) else cout<<"确定基数：1,第一个数；2,随机数；3，3个随机数的中位数；4，5个随机数的中位数：" int number; cin>>number; clock_t start,end;/计时 start=clock();_qsort(a,1,n,number);end

7、=clock();cout<<"用时："<<end-start<<"ms"<<endl;for(int i=1;i<=n;i+)cout<<ai<<" "return 0; 四、算法分析对数据进行快排，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 五、测试结果1以第一个数为基数的排序时间，单位ms.2以随

8、机数为基数的排序时间，单位ms3以三个随机数的中位数为基数的排序时间，单位ms4以五个随机数的中位数为基数的排序时间，单位ms（二）题目二一、问题Implement Hoares algorithm and compare it with our algorithm in the textbook. (体会有重复数据情况下，算法之间的优劣)。The input is also taken form 1000 and 10000 (between 0 and 50), and the tests should be done on the random input. The run times

9、must be plotted with respect to the sizes to illustrate the difference. (figure out using excel, matlab in the Report)二、问题分析实现Hoare快排算法，并和我们的快排算法相比较，即体会重复数据情况下，算法的优劣。三、算法伪代码void _qsort(a, p, r)if p<rq=Hoare_Partition(a,p,r);_qsort(a,p,q-1);_qsort(a,q+1,r); Hoare_Partition(a,p, r) x=ap i=p-1 j=r+1

10、while(1) while(1) j=j-1 if aj=x break while(1) i=i+1 if ai>=x break ifi<j swap(ai,aj) else return j main()int n,a200000cout<<"输入数据多少："cin>>nfor int i=1 i<=n i=i+1 ai=random(51)clock_t start ,endstart=clock() _qsort(a,1,n)end=clock()cout<<"运行时间："<<

11、end-start<<"ms"<<endlfor inti=1 i<=n i=i+1cout<<ai<<" "return 0四、算法分析相较原本算法，对Partition部分进行改变，原算法中，主元是与它所划分的两个分区分离的，而Hoare_Partition中主元是存在于两分区中的。五、测试结果（三）题目三一、问题Implement quicksort algorithm using tail recursion and compare it with the original quicksort

12、 algorithm.The input is also taken form 20000 and 100000 (between 0 and 50), and the tests should be done on the random input. The run times must be plotted with respect to the sizes to illustrate the difference. (figure out using excel, matlab in the Report)二、问题分析用尾递归实现快排，并和普通快排相比较，输入规模在1000-10000，

13、用运行时间和规模建立关系来显示不同。三、算法伪代码void Tail_qsort(a, p, r)while p<r q=Partition(a,p,r)Tail_qsort(a,p,q-1)p=q+1Partition( a, p, r) x=ap i=r+1for int j=r j>p j=j-1if aj>=x i=i-1swap(ai,aj)swap(ai-1,ap)return i-1main()int n,a200000cout<<"输入数据多少："cin>>nfor(int i=1;i<=n;i+) ai=random(51)clock_t start ,endstart=clock() Tai