The 4th question is my homework. I am asked to write 4 sort functions to compare the worst time they use. The length is n. My code is as follows
#include<vector>
using namespace std;
void Swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void partition(int *a, int left, int right){
int mid = (left+right)/2;
int t1 = a[left], t2 = a[mid], t3 = a[right];
if((t1 <= t2 && t2 <= t3) || (t3 <= t2 && t2 <= t1))
{Swap(a[right], a[mid]);}
else if((t2 <= t1 && t1 <= t3) || (t3 <= t1 && t1 <=t2))
{Swap(a[right], a[left]);}
}
void QuickSort(int* a,int left,int right)
{
if(left<right)
{
int i;
i=left;
int j;
j=right+1;
partition(a,left,right);
int mid = (left+right)/2;
int t1 = a[left], t2 = a[mid], t3 = a[right];
if((t1 <= t2 && t2 <= t3) || (t3 <= t2 && t2 <= t1))
{Swap(a[right], a[mid]);}
else if((t2 <= t1 && t1 <= t3) || (t3 <= t1 && t1 <=t2))
{Swap(a[right], a[left]);}
int pivot=a[left];
do{
do i++;while(a[i]<pivot);
do j--;while(a[j]>pivot);
if(i<j) Swap(a[i],a[j]);
}while(i<j);
Swap(a[left],a[j]);
QuickSort(a,left,j-1);
QuickSort(a,j+1,right);
}
}
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j-1]) {
Swap(arr[j], arr[j - 1]);
}
}
}
}
void Merge(int *initList,int* mergedList,int l,int m,int n)
{
int i1=l,iResult=l,i2=m+1;
for(;i1<=m&&i2<=n;iResult++)
{
if(initList[i1]<=initList[i2])
{
mergedList[iResult]=initList[i1];
i1++;
}
else
{
mergedList[iResult]=initList[i2];
i2++;
}
}
for(int temp=iResult;i1<m+1;i1++,temp++)
{
mergedList[temp]=initList[i1];
}
for(int temp=iResult;i2<n+1;i2++,temp++)
{
mergedList[temp]=initList[i2];
}
}
void MergePass(int *initList,int *resultList,int n,int s)
{
int i=1;
for(;i<=n-2*s+1;i+=2*s)
{
Merge(initList,resultList,i,i+s-1,i+2*s-1);
}
if((i+s-1)<n)Merge(initList,resultList,i,i+s-1,n);
else
for(int temp=i;temp<n+1;temp++)
{
resultList[temp]=initList[temp];
}
}
void MergeSort(int* a,int n)
{
int *tempList=new int[n+1];
for(int i=1;i<n;i*=2)
{
MergePass(a,tempList,n,i);
i*=2;
MergePass(tempList,a,n,i);
}
for(int i=0;i<n+1;i++)
{
a[i]=tempList[i];
}
delete[]tempList;
}
void adjustHeap(int* arr, int i, int length) {
int temp = arr[i];//先取出当前元素i
for (int k = i * 2 + 1; k <=length; k = k * 2 + 1) {
if (k + 1 <=length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}
void adjust_heap(int* a, int father, int len)
{
int left = 2 * father;
int right = 2 * father + 1;
int max = father;
if( left <= len && a[left] > a[max])
max = left;
if( right <= len && a[right] > a[max])
max = right;
if(max != father)
{
Swap( a[max], a[father]);
adjust_heap(a, max, len);
}
}
void HeapSort(int* a, int len)
{
for(int i = len / 2; i >= 1; --i)
adjust_heap(a, i, len);
for(int i = len; i >= 1; --i)
{
Swap(a[1], a[i]);
adjust_heap(a, 1, i - 1);
}
for(int i=0;i<len;i++)
a[i]=a[i+1];
}
void heapAdjust(int*nums, int idx,int len){
int temp=nums[idx];
for(int j=idx*2+1;j<len;j=j*2+1){
if(j+1<len&&nums[j]<nums[j+1]) {j++;}
if(temp>nums[j]) {break;}
nums[idx]=nums[j];
idx =j;
}
nums[idx]=temp;
}
void heapSort(int* nums, int n,int k){
for(int i=n/2-1;i>=0;i--)
{
heapAdjust(nums, i,n);
}
for(int i=n-1;i>0;i--)
{
if(k) {k--;}
else {break;}
swap(nums[0],nums[i]);
heapAdjust(nums,0,i);
}
}
void MaxMerge(int arr[],int l,int r)//transform the array so it is the most complex for merge sorting
{
if(r-l>1)
{
int *temp=new int[r-l+3];
temp[0]=0;
for(int i=0,j=1;i<=r-l;i++)
{
if(i%2==0){
temp[j+(r-l+1)/2]=arr[i+l];
}
else{
temp[j]=arr[i+l];
j++;
}
}
for(int i=l,j=1;i<=r;)
{
arr[i]=temp[j];
i++;
j++;
}
delete[]temp;
MaxMerge(arr,l+(r-l)/2,r);
MaxMerge(arr,l,l+(r-l)/2-1);
}
else
{
int t=arr[l];
arr[l]=arr[r];
arr[r]=t;
}
}
void Permute(int *a,int n)
{
srand(time(0));
for(int i=n;i>=2;i--)
{
int j=rand()%i+1;
swap(a[j],a[i]);
}
}
void TimeTest(int n)
{
if(n!=0){
int *QuickSortTest=new int[n+1];
int *InsertSortTest=new int[n+1];
int *HeapSortTest=new int[n+1];
int *MergeSortTest=new int[n+1];
for(int j=0;j<n+1;j++)
{
QuickSortTest[j]=j;
InsertSortTest[j]=n-j;
MergeSortTest[j]=j;
HeapSortTest[j]=j;
}
MaxMerge(MergeSortTest,1,n);
Permute(HeapSortTest,n);
clock_t begin1=clock();
for(int j=0;j<500;j++)
{
QuickSort(QuickSortTest,1,n);
}
clock_t end1=clock();
clock_t begin2=clock();
for(int j=0;j<500;j++)
{
heapSort(HeapSortTest,n,n-1);
}
clock_t end2=clock();
clock_t begin3=clock();
for(int j=0;j<500;j++)
{
InsertSort(QuickSortTest,n);
}
clock_t end3=clock();
clock_t begin4=clock();
for(int j=0;j<500;j++)
{
MergeSort(QuickSortTest,n);
}
clock_t end4=clock();
cout<<"n="<<n<<" QuickSort: "<<end1-begin1<<endl;
cout<<"n="<<n<<" HeapSort: "<<end2-begin2<<endl;
cout<<"n="<<n<<" InsertSort: "<<end3-begin3<<endl;
cout<<"n="<<n<<" MergeSort: "<<end4-begin4<<endl;
delete[]QuickSortTest;
delete[]InsertSortTest;
delete[]HeapSortTest;
delete[]MergeSortTest;
}
}
int main()
{
//int num1[]={500,1000,2000,4000,3000};
for(int i=0;i<=4000;i+=100)
{TimeTest(i);cout<<endl;}
}
I have already test for every function, and they are all right.
However,the result is that
I am confused that why merge sorting is always the quickest?
