Исходник сравнения сортировки методом простых вставок с сортировкой методом турнир с выбыванием


Добавил:DMT
Дата создания:25 апреля 2008, 12:44
Дата обновления:25 апреля 2008, 12:44
Просмотров:3999 последний вчера, 16:51
Комментариев: 0

Исходник сравнения сортировки методом простых вставок с сортировкой методом турнир с выбыванием

Код на C++
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4. #include <conio.h>
  5.  
  6.  
  7. int count=0,sr=0;//количество копирований и сравнений
  8. clock_t start,end;
  9. int t[4000];
  10. int shell[4]={8,4,2,1};
  11. int x[101];
  12.  
  13. //сортировка вставками
  14. void insert (int n)
  15. {
  16. int i, j, t;
  17. for (i=1; i<n; i++)
  18. {
  19. t=x[i];count++;
  20. for (j=i-1; j>=0 && t<x[j]; j--,sr++)//двигаемся снизу вверх
  21. {//пока t не больше или равно x[j]
  22. count++;
  23. x[j+1]=x[j];//сдвиг на одну позицию
  24. }
  25. x[j+1]=t;count++;
  26. }
  27. }
  28.  
  29.  
  30. void sort(int n)
  31. {
  32. for(int i=0;i<n-1;i++)
  33. {
  34. int k=i;
  35. for(int j=i+1;j<n;j++,count++)
  36. if(t[k]>t[j]) k=j;
  37. if (k!=i)
  38. {
  39. int r=t[k];
  40. t[k]=t[i];
  41. t[i]=r;
  42. sr++;
  43. }
  44. }
  45. }
  46.  
  47. void sort2 (void)
  48. {
  49. for(int i=0;i<4;i++)
  50. {
  51. int x1=shell[i];
  52. for(int j=0;j<x1;j++)
  53. {
  54. int k=0,l=j;
  55. while (l<102)
  56. {
  57. t[k]=x[j+k*x1];
  58. l+=shell[i];
  59. k++;
  60. }
  61. sort (k);
  62. for(l=0;l<k;l++) x[j+l*x1]=t[l];
  63. }
  64. }
  65. }
  66. void main(void)
  67. {
  68. int a[101];
  69. int i;
  70. clrscr();
  71. randomize(); //случайный выбор первого числа
  72. for (i=0; i<=100; i++)
  73. a[i]=x[i]=random(200); //случайное число 0-199
  74.  
  75. printf("Сортировка методом простых вставок\n");
  76. start=clock();
  77. insert (100);
  78. end=clock(); //вызов подпрограммы сортировки
  79. for (i=0; i<100; i++)
  80. printf("%3d ",x[i]);
  81. printf("\nЧисло сортируемых элементов: 100");
  82. printf("\nЧисло сравнений: %i",sr);sr=0;
  83. printf("\nЧисло копирований: %i",count);count=0;
  84. printf("\nВремя сортировки: %f сек",(end-start)/CLK_TCK);
  85.  
  86. for(i=0;i<=100;i++)
  87. x[i]=a[i-1];
  88.  
  89. printf("\n\nТурнир с выбыванием\n");
  90.  
  91. start=clock();
  92. sort2 ();
  93. end=clock();
  94.  
  95. for(i=1; i<=100; i++)
  96. printf("%3d ",x[i]);
  97. printf("\nЧисло сортируемых элементов: 100");
  98. printf("\nЧисло сравнений: %i",sr);
  99. printf("\nЧисло копирований: %i",count);
  100. printf("\nВремя сортировки: %f сек",(end-start)/CLK_TCK);
  101.  
  102. getch();
  103.  
  104. }
При использовании обязательна ссылка на http://DMTSoft.ru
up