Facebook
From Mrkazik99, 3 Years ago, written in C.
Embed
Download Paste or View Raw
Hits: 194
  1. #include <stdio.h>
  2. #include <time.h>
  3.  
  4. int arrI[3000];
  5.  
  6. void randomArray (int index) {
  7.     for (int i=0;i<index;i++) {
  8.         arrI[i]=rand()%10000;
  9.     }
  10.     return;
  11. }
  12.  
  13. void ShellSortChar (char arr[], int index) {
  14.     int help, j, porownan=0, zmian=0;
  15.     char x, a[5];
  16.     a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;
  17.     for(int k=0;k<5;k++) {
  18.         help=a[k];
  19.         for(int i=help;i<index;++i) {
  20.             x=arr[i];
  21.             porownan++;
  22.             for(j=i-help;(x<arr[j]) && (k>=0);j=j-help) {
  23.                 arr[j+help] = arr[j];
  24.                 zmian++;
  25.             }
  26.             arr[j+help] = x;
  27.         }
  28.     }
  29.     printf("Wykonano %d zmian i %d porownan", zmian, porownan);
  30.     return;
  31. }
  32.  
  33. void ShellSortInt (int arr[], int index) {
  34.     int help, j, porownan=0, zmian=0;
  35.     int x, a[6];
  36.     a[0]=1; a[1]=7; a[2]=1; a[3]=48; a[4]=191; a[5]=514;
  37.     for(int k=0;k<6;k++) {
  38.         help=a[k];
  39.         for(int i=help;i<index;++i) {
  40.             x=arr[i];
  41.             porownan++;
  42.             for(j=i-help;(x<arr[j]) && (k>=0);j=j-help) {
  43.                 arr[j+help] = arr[j];
  44.                 zmian++;
  45.             }
  46.             arr[j+help] = x;
  47.         }
  48.     }
  49.     printf("Wykonano %d zmian i %d porownan\n", zmian, porownan);
  50.     return;
  51. }
  52.  
  53. void ShellSortIntAlt (int arr[], int index) {
  54.     int help, j, porownan=0, zmian=0;
  55.     int x, a[3000];
  56.     a[0]=5;
  57.     for(int i=1;i<index;i++){
  58.         a[i]=4*a[i-1]+2;
  59.     }
  60.     for(int k=0;k<6;k++) {
  61.         help=a[k];
  62.         for(int i=help;i<index;++i) {
  63.             x=arr[i];
  64.             porownan++;
  65.             for(j=i-help;(x<arr[j]) && (k>=0);j=j-help) {
  66.                 arr[j+help] = arr[j];
  67.                 zmian++;
  68.             }
  69.             arr[j+help] = x;
  70.         }
  71.     }
  72.     printf("Wykonano %d zmian i %d porownan\n", zmian, porownan);
  73.     return;
  74. }
  75.  
  76. void sortB (int arr1[], int index1) {
  77.     int porownan=0, zmian = 0, swap;
  78.     for(int i=0;i<=index1;i++){
  79.         for(int j=index1;j>=i+1;j--){
  80.             porownan++;
  81.             if(arr1[j]<arr1[j-1]){
  82.                 swap = arr1[j-1];
  83.                 arr1[j-1]=arr1[j];
  84.                 arr1[j]=swap;
  85.                 zmian++;
  86.             }
  87.         }
  88.     }
  89.     printf("\nBabelkowe: %d, %u, %u\n", index1, porownan, zmian);
  90.     return;
  91. }
  92.  
  93. int main()
  94. {
  95.     int length = 12;
  96.     /*char arr[12][1] = {"E","A","S","Y","Q","U","E","S","T","I","O","N"};
  97.     for(int i=0;i<length;i++){
  98.         printf("%c", *arr[i]);
  99.     }
  100.     printf("\n");
  101.     ShellSortChar(arr, length);
  102.     printf("\n");
  103.     for(int i=0;i<length;i++){
  104.         printf("%c", *arr[i]);
  105.     }
  106.     printf("\n");
  107.     length = 200;
  108.     randomArray(length);
  109.     for(int i=0;i<length;i++) {
  110.         printf("%d, ", arrI[i]);
  111.     }
  112.     printf("\n");
  113.     ShellSortInt(arrI, length);
  114.     printf("\n");
  115.     for(int i=0;i<length;i++) {
  116.         printf("%d, ", arrI[i]);
  117.     }
  118.     printf("\n");*/
  119.     for(int i=100;i<=3000;i+=100) {
  120.         randomArray(i);
  121.         ShellSortIntAlt(arrI, i);
  122.     }
  123.     printf("\n");
  124.     for(int i=100;i<=3000;i+=100) {
  125.         randomArray(i);
  126.         ShellSortInt(arrI, i);
  127.     }
  128.     printf("\n");
  129.     for(int i=100;i<=3000;i+=100) {
  130.         randomArray(i);
  131.         sortB(arrI, i);
  132.     }
  133. }