Исходник сравнения обменной поразрядной сортировки с сортировкой методом Шеллацу


Добавил:DMT
Дата создания:25 апреля 2008, 12:02
Дата обновления:25 апреля 2008, 12:02
Просмотров:5307 последний вчера, 19:56
Комментариев: 0

Исходник сравнения обменной поразрядной сортировки с сортировкой методом Шелла 

Код на C++
  1.  
  2. #include <stdio.h>
  3. #include <conio.h>
  4. #include <math.h>
  5. #include <string.h>
  6. #include <time.h>
  7.  
  8. clock_t start,end;
  9. long comp,repl;
  10. unsigned int a[4000],t[4000];
  11. int shell[4]={8,4,2,1};
  12. int n;
  13.  
  14. void sort1(int l,int r,int b)
  15. {
  16. 	if (l>=r) return;
  17. 	int i=l,j=r,t;
  18. 	while(i<j)
  19. 	{
  20. 		for(;i<j;i++) {comp++; if (((a[i]>>b)&1)==1) break;}
  21. 		if (i==j) break;
  22. 		for(;i<j;j--) {comp++;if (((a[j]>>b)&1)==0) break;}
  23. 		if (i==j) break;
  24. 		repl++;
  25. 		t=a[i],a[i]=a[j],a[j]=t,i++,j--;
  26. 	}
  27. 	if (b==0) return;
  28. 	if(((a[i]>>b)&1)==1)
  29. 	{
  30. 			sort1(l,i-1,b-1);
  31. 			sort1(i,r,b-1);
  32. 	}
  33. 	else
  34. 	{
  35. 			sort1(l,i,b-1);
  36. 			sort1(i+1,r,b-1);
  37. 	}
  38. }
  39.  
  40. void sort(int n)
  41. {
  42. 	for(int i=0;i<n-1;i++)
  43. 	{
  44. 		int k=i;
  45. 		for(int j=i+1;j<n;j++,comp++)
  46. 		if(t[k]>t[j]) k=j;
  47. 		if (k!=i)
  48. 		{
  49. 			int r=t[k];
  50. 			t[k]=t[i];
  51. 			t[i]=r;
  52. 			repl++;
  53. 		}
  54. 	}
  55. }
  56.  
  57. void sort2 (void)
  58. {
  59. 	for(int i=0;i<4;i++)
  60. 	{
  61. 		int x=shell[i];
  62. 		for(int j=0;j<x;j++)
  63. 		{
  64. 		int k=0,l=j;
  65. 		while (l<n)
  66. 		{
  67. 			t[k]=a[j+k*x];
  68. 			l+=shell[i];
  69. 			k++;
  70. 		}
  71. 		sort (k);
  72. 		for(l=0;l<k;l++) a[j+l*x]=t[l];
  73. 		}
  74. 	}
  75. }
  76.  
  77. void main (void)
  78. {
  79. 	FILE *in,*out1,*out2;
  80. 	if ((in=fopen("s:\\in.txt","r"))==NULL) return;
  81. 	if ((out1=fopen("s:\\out1.txt","w"))==NULL) return;
  82. 	if ((out2=fopen("s:\\out2.txt","w"))==NULL) return;
  83.  
  84. 	int i=0,r=0;
  85. 	while(1)
  86. 	{
  87. 			if (feof(in)) break;
  88. 			fscanf(in,"%d",&a[n]);
  89. 			if(a[n]>i) i=a [n];
  90. 			n++;
  91. 	}
  92. 	while(i) r++,i=i>>1;
  93.  
  94. 		start=clock();
  95. 		sort1(0,n-1,r-1);
  96. 		end=clock();
  97.  
  98. 	for(i=0;i<n;i++)
  99. 	fprintf(out1,"%d\n",a[i]);
  100. 	fprintf(out1,"Porazr Sort\n");
  101. 	fprintf(out1,"Compares: %ld\nSwitches: %ld\n",comp,repl);
  102. 	fprintf(out1,"Time: %f",(end-start)/CLK_TCK);
  103. 	fclose(out1);
  104.  
  105. 	n=0,comp=0,repl=0;
  106. 	fseek(in,0,0);
  107. 	while(1)
  108. 	{
  109. 		if (feof(in)) break;
  110. 		fscanf(in,"%d",&a[n]);
  111. 		n++;
  112. 	}
  113. 	fclose(in);
  114.  
  115. 	start=clock();
  116. 	sort2();
  117. 	end=clock();
  118. 	for(i=0;i<n;i++)
  119. 	fprintf(out2,"%d\n",a[i]);
  120. 	fprintf(out2,"Shell  Sort\n");
  121. 	fprintf(out2,"Compares: %ld\nSwitches: %ld\n",comp,repl);
  122. 	fprintf(out2,"Time: %f",(end-start)/CLK_TCK);
  123. 	fclose(out2);
  124. }
  125.  
При использовании обязательна ссылка на http://DMTSoft.ru

Результаты работы программы:

Входные данные: 1 23 45 654 56 354 65 565 65 2 64 897 999 654 123 98 8

Выходные данные:
Обменная поразрядная сортировка:
1 2 8 23 45 56 64 65 65 98 123 354 565 654 654 897 999
Porazr Sort Compares: 101 Switches: 15 Time: 0.000000

Сортировка Шелла:
1 2 8 23 45 56 64 65 65 98 123 354 565 654 654 897 999
Shell Sort Compares: 238 Switches: 21 Time: 0.000000

up