快速排序和歸并排序代碼

1、Merge Sort and QuicksortPrerequisites, Goals, and OutcomesPrerequisitesStude nts should have mastered the followi ng prerequisite skills.« MergeSort -Merge Sort Algorithm* QuickSort - QuickSort AlgorithmGoals: This programming assignmentsimproves the performanee of merge sort by implementing a

2、non-recursive, semi-in-plaee version of the merge-sort algorithm.Outcomes: Students successfully eompleting this assignment would master the followi ng outcomes.« Un dersta nd the Merge Sort algorithm and comparis ons of differe nt algorithms« Un dersta nd the QuickSort algorithmDescriptio

3、nThe students are supposed to refer to the lecture for more information about MergeSort and QuickSort. No more material is provided in this secti on.In-Place SortingIn-place sorting is to sort data items without using additional arrays. For instanee, quick sort performs partiti oning operati ons by

4、simply repeat ing a swapp ing operatio n on two data items in a give n array, which thus n eeds no extra arrays.On the other hand, merge sort we have studied allocates a temporary array, sorts partial data items in that array, and copies them back to the orig inal array at each recursive call. Due t

5、o this repetitive array-copy ing operati ons, merge sort is much slower tha n quick sort although their running time is upper-bounded to O(n log n).It has bee n an research in terest to develop in-place merge sort algorithms, almost all of which are however impractically complicated. Yet, we can imp

6、rove the performa nee of merge sort with addi ng the followi ng two restricti ons:1. Using a non-recursive method2. Using only one additional array (i.e., a semi-i n-place method).Merge data from the orig inal in to the additi onal array at the very bottom stage, and thereafter perform the next merg

7、e from the additi onal in to the origi nal array, in which way merge operati ons are applied to the orig inal and additi onal array in turn as you go through each repetitive stage. Don't copy back in termediate results to the origi nal array at the end of each stage for the purpose of always mer

8、gi ng data from the orig inal to the additional array.Note that we still need to allow data items to be copied between the original and this additional arrays as many times asO(log n).TaskDesign and implement a non-recursive, semi-in-place version of the merge-sort algorithm. The frameworks of the t

9、hree algorithms are given in file quicksort.cpp, mergesort.cpp and mergeImproved.cpp respectively.Needless to say, mergeImproved( ) function must not call itself or some other recursive functions. Furthermore, the algorithm should still be based on the same divide-and-conquer approach.Use the main f

10、unction to verify and evaluate the performance of your non-recursive, semi-in-place merge sort program.Compare the performance among the usual quicksort, the usual mergesort, and your improved mergesort as increasing the array size = 10, 100, 1000, and 10000.SubmitSubmit only the following. quicksor

11、t.cpp mergesort.cpp mergeImproved.cpp#include<iostream> using namespace std;#include<iostream>using namespace std; class sort private: int Array10; int left,right;/merge sorting public:sort();void MergeSort(int Array,int TempArray,int left,int right) int middle; if(left<right) middle=

12、(left+right)/2;MergeSort(Array,TempArray,left,middle);MergeSort(Array,TempArray,middle+1,right);Merge(Array,TempArray,left,right,middle);void Merge(int Array,int TempArray,int left,int right,int middle)int i,j,index1,index2;for(j=left;j<=right;j+)TempArrayj=Arrayj;index1=left;index2=middle+1;i=le

13、ft;while(index1<=middle&&index2<=right)if(TempArrayindex1<=TempArrayindex2)Arrayi+=TempArrayindex1+;elseArrayi+=TempArrayindex2+;while(index1<=middle)Arrayi+=TempArrayindex1+;while(index2<=right)Arrayi+=TempArrayindex2+;/quick sortvoid QuickSort(int Array,int left,int right)if

14、(right<=left)return;int pivot=SelectPivot(left,right);swap(Array,pivot,right);pivot=Partition(Array,left,right);QuickSort(Array,left,pivot-1);QuickSort(Array,pivot+1,right);int SelectPivot(int left,int right)return (left+right)/2;void swap(int Array,int pivot,int right)int temp;Arrayright+1=Array

15、pivot-1;int Partition(int Array,int left,int right)int l=left;int r=right;int TempRecord=Arrayr;while(l!=r)while(Arrayl<=TempRecord&&r>l) l+;if(l<r)Arrayr=Arrayl;r-; while(Arrayr>=TempRecord&&r>l) r-;if(l<r)Arrayl=Arrayr;l+;Arrayl=TempRecord;return l;void main()sort t1;int Array10;int TempArray10;int i,chose;cout<<" 請輸入你要排序的數(shù) "<<endl;for(i=0;i<10;i+) cin>>Arrayi;cout<<" 需預(yù)排序的數(shù)如下所示 "<<endl; for(i=0;i<10;i+) cout<<Arrayi<<" "2 選用cout«"請選擇你的排序方案(輸入1選用MergeSo