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


Добавил:DMT
Дата создания:25 апреля 2008, 12:02
Дата обновления:25 апреля 2008, 12:02
Просмотров:4480 последний позавчера, 0:23
Комментариев: 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