| 站点地图 | 联系我
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 上善若水 厚德载物
 现在位置 :: 主页 >> 资料中心 >> ROOT / CODE / ARITHMETIC /
 

排序算法比较程序

来源(编程开发 - 新云网络)

From: http://www.newasp.net/tech/program/20575.html

排序算法比较程序

作者:佚名 来源:本站整理 发布时间:2006-3-27 17:17:43

功能要求如下:

排序算法比较: shellsort, quicksort, heapsort, mergesort 的算法实现 ,
对同样数据集的排序时间比较。

源代码:

# include <stdio.h>
# include <time.h>

# define MAXSIZE 2000

typedef struct{
	int key[MAXSIZE];
	int length;
}list;

long int  compCount;
long int  shiftCount;

void menu(int *m)/*retun m*/
{
	int i;
	char menu[6][15]={"1 CREATE ","2 IMPORT ","3 SORT","4 SHOW RESULT",
		"5 SAVE RESULT","6 EXIT"};
	
	clrscr();
	printf("SORT COMPARE SYSTEM");
	for (i=0;i<6;i++) printf("%s",menu[i]);
	printf(" Please Select (1-6):");
	
	scanf("%d",m);
	
}

void menusort(int *m)/*retun m*/
{
	int i;
	char menusort[5][15]={"1 SHELL SORT","2 QUICK SORT","3 HEAP SORT",
		"4 MERGE SORT","5 ALL SORT"};
	
	clrscr();
	printf("SORT");
	for(i=0;i<5;i++) printf("%s",menusort[i]);
	printf(" Please Select (1-5):");
	
	scanf("%d",m);
	
}

void menushow(int *m)/*retun m*/
{
	int i;
	char menushow[4][20]={"1 SHELL SORT RESULT","2 QUICK SORT RESULT",
		"3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
	
	clrscr();
	printf("SHOW SORT RESULT");
	for(i=0;i<4;i++) printf("%s",menushow[i]);
	printf(" Please Select (1-4):");
	
	scanf("%d",m);
	
}

void menusave(int *m) {
	int i;
	char menusave[4][20]={"1 SHELL SORT RESULT","2 QUICK SORT RESULT",
		"3 HEAP SORT RESULT","4 MERGE SORT RESULT"};
	
	clrscr();
	printf("SAVE:");
	for (i=0;i<4;i++) printf("%s",menusave[i]);
	printf(" Please Select (1-4):");
	
	scanf("%d",m);
}

void create(list *L) {
	int i;
	
	printf("HOW MANY DATA?");
	scanf("%d",&((*L).length));
	
	for(i=1;i<=(*L).length;i++) {
		printf("PLEASE INPUT THE %dth DATA:",i);
		scanf("%d",&(*L).key[i]);
	}
	printf("CREATE COMPLETE !");
	
}

int listopen(list *L,char *filename) {
	int k=1;
	FILE *data;
	
	data=NULL;
	
	data=fopen(filename,"rb");
	
	while (! feof(data)) {
		fscanf(data,"%d",&(*L).key[k]);
		k++;
	}
	(*L).length=k-1;
}

void import(list *L)/*fix L*/
{
	char filename[255];
	int i;
	
	printf("PLEASE INPUT THE FILE PATH AND NAME:");
	scanf("%s",filename);
	
	clrscr();
	listopen(L,filename);
	for(i=1;i<(*L).length;i++) printf("%d ",(*L).key[i]);
	printf("PRESS ANYKEY RETURN TO MAINMENU...");
	getch();
}

void save(list L)
{
	FILE *data;
	char filename[255];
	int r;
	
	printf("PLEASE INPUT THE FILE PATH AND NAME:");
	scanf("%s",filename);
	
	data=fopen(filename,"wb");
	for(r=1;r<=L.length;r++) fprintf(data,"%d",L.key[r]);
	fclose(data);
	printf("SAVE OK! PRESS ANY KEY TO RETURN THE MAINMENU... ");
	getch();
	
}

list shellsort(list L)/*retun L_SHELL*/
{
	int i,j,gap,x,n;
	
	compCount=shiftCount=0;
	n=L.length;
	gap=n/2;
	while (gap>0) {
		compCount++;
		for(i=gap+1;i<=n;i++) {
			compCount++;
			j=i-gap;
			while(j>0) {
				compCount++;
				if(L.key[j]>L.key[j+gap]) {
					compCount++;
					x=L.key[j];shiftCount++;
					L.key[j]=L.key[j+gap];shiftCount++;
					L.key[j+gap]=x;shiftCount++;
					j=j-gap;
				}
				else j=0;
			}
			
		}
		gap=gap/2;
	}
	return L;
}

void shell(list L,list *LS,float *timeshell)/*return LS,timeshell.
MUST add an "getch"!!*/
{
	clock_t start,end;
	
	start=clock();
	(*LS)=shellsort(L);
	end=clock();
	
	*timeshell=(end-start)/CLK_TCK;
	
	printf("SHELLSORT COST TIME :%f SECONDS.",*timeshell);
	printf("Compare %d times.Shfit %d times.",compCount,shiftCount);
}

int Partition(list * pL,int low,int high) {
	int pivotkey;
	pL->key[0]=pL->key[low];shiftCount++;
	pivotkey=pL->key[low];shiftCount++;
	while(low<high)
	{
		compCount++;
		while(low<high && pivotkey<=(pL->key[high]))
		{compCount++;compCount++; --high;}
		pL->key[low]=pL->key[high];shiftCount++;
		while(low<high && (pL->key[low])<=pivotkey)
		{compCount++;compCount++; ++low;}
		pL->key[high]=pL->key[low];shiftCount++;
	}
	pL->key[low]=pL->key[0];shiftCount++;
	return low;
}/*Partition*/

void QSort(list * pL,int low,int high) {
	int pivotloc;
	if(low<high)
	{
		compCount++;
		pivotloc=Partition(pL,low,high);
		QSort(pL,low,pivotloc-1);
		QSort(pL,pivotloc+1,high);
	}
}/*QSort*/

list QuickSort(list pL) {
	compCount=shiftCount=0;
	QSort(&pL,1,pL.length);
	return pL;
}/*QuickSort*/

void quick(list L,list *LQ,float *timequick)/*MUST add an "getch"!!*/
{
	clock_t start,end;
	
	start=clock();
	(*LQ)=QuickSort(L);
	end=clock();
	
	*timequick=(end-start)/CLK_TCK;
	
	printf("QUICKSORT COST TIME :%f SECONDS.",*timequick);
	printf("Compare %d times.Shfit %d times.",compCount,shiftCount);
}

void sift(list L,int l,int m) {
	int i,j,x;
	i=l;
	j=2*i;
	x=L.key[i];
	while (j<=m)
	{
		compCount++;
		if(j<m && L.key[j]<L.key[j+1]) {j++;compCount++;compCount++;}
		if(x<L.key[j])
		{
			compCount++;
			L.key[i]=L.key[j];shiftCount++;
			i=j;shiftCount++;
			j=2*i;
		}
		else j=m+1;
	}
	L.key[i]=x;shiftCount++;
}

list heapsort(list L) {
	int i,w;
	
	compCount=shiftCount=0;
	for (i=L.length/2;i>=1;i--) {sift(L,i,L.length);compCount++;}
	for (i=L.length;i>=2;i--)
	{
		compCount++;
		w=L.key[i];shiftCount++;
		L.key[i]=L.key[1];shiftCount++;
		L.key[1]=w;shiftCount++;
		sift(L,i-1,1);
	}
	return L;
}

void heap(list L,list *LH,float *timeheap) {
	clock_t start,end;
	
	start=clock();
	(*LH)=heapsort(L);
	end=clock();
	
	*timeheap=(end-start)/CLK_TCK;
	
	printf("HEAPSORT COST TIME :%f SECONDS.",*timeheap);
	printf("Compare %d times.Shfit %d times.",compCount,shiftCount);
}

void Merge(int source[],int result[],int size,int n) {
	int lb1,lb2,ub1,ub2,p,i,j;
	lb1=0;
	p=0;
	while((lb1+size)<n) {
		compCount++;
		lb2=lb1+size;
		ub1=lb2-1;
		if((lb2+size-1)>n)
		{ ub2=n-1; compCount++; shiftCount++;}
		else
		{ub2=lb2+size-1; compCount++; shiftCount++;}
		i=lb1;
		j=lb2;
		while((i<=ub1)&&(j<=ub2)) {
			compCount++;compCount++;
			if(source[i]<=source[j])
			{result[p++]=source[i++]; shiftCount++; compCount++;}
			else
			{result[p++]=source[j++]; shiftCount++; compCount++;}
		}
		while(i<=ub1)
		{result[p++]=source[i++]; shiftCount++; compCount++;}
		while(j<=ub2)
		{result[p++]=source[j++]; shiftCount++; compCount++;}
		lb1=ub2+1;
	}
	i=lb1;
	while(p<n)
	{compCount++; result[p++]=source[i++];shiftCount++;}
}

void Mergesort(list *L) {
	int n=(*L).length;
	int s=1;
	int *temp=(int *)malloc(n*sizeof(int));
	compCount=shiftCount=0;
	
	if (temp==NULL) {
		printf("out of memory");
		return;
	} while(s<n) {
		compCount++;
		Merge((*L).key,temp,s,n);
		s*=2;
		Merge(temp,(*L).key,s,n);
		s*=2;
	}
	compCount++;
}

void domerge(list L,list *LM,float *timemerge)/*MUST add an "getch"!!*/
{
	clock_t start,end;
	
	start=clock();
	Mergesort(&L);
	
	end=clock();
	(*LM)=L;
	*timemerge=(end-start)/CLK_TCK;
	
	printf("MERGESORT COST TIME :%f SECONDS.",*timemerge);
	printf("Compare %d times.Shfit %d times.",compCount,shiftCount);
}

main() {
	list L,LS,LQ,LH,LM;
	int LOCK3=0,LOCK4=0,LOCK5=0,RUN=1,LOCK41=0,LOCK42=0,LOCK43=0,LOCK44=0;
	int comd,r;
	float timeshell,timequick,timeheap,timemerge;
	
	while(RUN==1) {
start:
        menu(&comd);
        switch (comd) {
        case 1:
            create(&L);
            LOCK3=1;
            break;
        case 2:
            import(&L);
            LOCK3=1;
            goto start;
        case 3:
            if(LOCK3==0) goto start;
            menusort(&comd);
            LOCK4=1;
            LOCK5=1;
            switch (comd) {
            case 1:
                LOCK41=1;
                shell(L,&LS,×hell);
                printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                getch();
                goto start;
            case 2:
                LOCK42=1;
                quick(L,&LQ,&timequick);
                printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                getch();
                goto start;
            case 3:
                LOCK43=1;
                heap(L,&LH,&timeheap);
                printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                getch();
                goto start;
            case 4:
                LOCK44=1;
                domerge(L,&LM,&timemerge);
                printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                getch();
                goto start;
            case 5:
                LOCK41=1;
                LOCK42=1;
                LOCK43=1;
                LOCK44=1;
                shell(L,&LS,×hell);
                quick(L,&LQ,&timequick);
                heap(L,&LH,&timeheap);
                domerge(L,&LM,&timemerge);
                printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
                getch();
                goto start;
            case 6:
                goto start;
            }
		case 4:
			if(LOCK4==0) goto start;
			menushow(&comd);
			switch(comd) {
			case 1:
				if(LOCK41==0) goto start;
				for (r=1;r<=LS.length;r++)
					printf("%d",LS.key[r]);
				printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
				getch();
				goto start;
			case 2:
				if(LOCK42==0) goto start;
				for (r=1;r<=LQ.length;r++)
					printf("%d",LQ.key[r]);
				printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
				getch();
				goto start;
			case 3:
				if(LOCK43==0) goto start;
				for (r=1;r<=LH.length;r++)
					printf("%d",LH.key[r]);
				printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
				getch();
				goto start;
			case 4:
				if(LOCK44==0) goto start;
				for (r=1;r<=LM.length;r++)
					printf("%d",LM.key[r]);
				printf(" PRESS ANY KEY TO RETURN MAIN MENU... ");
				getch();
				goto start;
			case 6:
				goto start;
			}
        case 5:
            if(LOCK5==0) goto start;
            menusave(&comd);
            switch (comd) {
            case 1:
                if(LOCK41==0) goto start;
                save(LS);
                break;
            case 2:
                if(LOCK42==0) goto start;
                save(LQ);
                break;
            case 3:
                if(LOCK43==0) goto start;
                save(LH);
                break;
            case 4:
                if(LOCK44==0) goto start;
                save(LM);
                break;
            case 6:
                break;
                
            }
            break;
        case 6:
            exit(0);
        }
    }
}


[本日:1 本周:1 本月:13 总数:3520 ]

Link: http://www.asm32.net/article_details.aspx?id=4330


浏览次数 135 发布时间 2008/11/23 5:50:36 从属分类 ARITHMETIC 【评论】【 】【打印】【关闭
 
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 京ICP备09029108号-1