Facebook
From ja, 9 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 592
  1. #include "stdafx.h"
  2. #include "time.h"
  3. #include <iostream>
  4.  
  5.  
  6. using namespace std;
  7. unsigned long int const n = 20000000;
  8.  
  9. float z[n+1];
  10.  
  11. void bubble_sort(unsigned long int n, float *a)
  12. {
  13.         unsigned long int l, k;
  14.         float p;
  15.         l = n;
  16.         do
  17.         {
  18.                 l = l - 1; k = 0;
  19.                 for (unsigned long int i = 1; i <= l; i++)
  20.                 if (a[i] > a[i + 1])
  21.                 {
  22.                         p = a[i]; a[i] = a[i + 1]; a[i + 1] = p; k = k + 1;
  23.                 }
  24.         } while (k != 0);
  25. }
  26.  
  27. void sort_insert(unsigned long int n, float *a)
  28. {
  29.  
  30.         float y, w;
  31.         unsigned long int l, p, s, k;
  32.         w = -1.7e38;
  33.         a[0] = w;
  34.         for (unsigned long int i = 2; i <= n; i++)
  35.         {
  36.                 y = a[i]; l = 0; p = i - 1;
  37.                 do
  38.                 {
  39.                         s = (l + p + 1) / 2;
  40.                         if (a[s] <= y)l = s; else p = s - 1;
  41.                 } while (l != p);
  42.                 k = l;
  43.                 for (unsigned long int j = i - 1; j >= k + 1; j--)
  44.                         a[j + 1] = a[j];
  45.                 a[k + 1] = y;
  46.         }
  47. }
  48.  
  49. void scaluj(unsigned long int l, unsigned long int s, unsigned long int p, float *a)
  50. {
  51.         //float z[n + 1];
  52.         unsigned long int i, j, m, k;
  53.         i = l; j = s; m = l;
  54.         do
  55.         {
  56.                 if (a[i] <= a[j])
  57.                 {
  58.                         z[m] = a[i]; i = i + 1;
  59.                 }
  60.                 else { z[m] = a[j]; j = j + 1; }
  61.                 m = m + 1;
  62.         } while (i < s && j <= p);
  63.         if (i < s)
  64.         {
  65.                 k = p;
  66.                 for (unsigned long int j = s - 1; j >= i; j--)
  67.                 {
  68.                         a[k] = a[j];
  69.                         k = k - 1;
  70.                 }
  71.         }
  72.         for (unsigned long int i = l; i <= m - 1; i++)
  73.                 a[i] = z[i];
  74. }
  75. void sort_scal(unsigned long int d, unsigned long int g, float *a)
  76. {
  77.         unsigned long int s;
  78.         if (d < g)
  79.         {
  80.                 s = (d + g) / 2;
  81.                 sort_scal(d, s, a);
  82.                 sort_scal(s + 1, g, a);
  83.                 scaluj(d, s + 1, g, a);
  84.         }
  85. }
  86. void quick_sort(unsigned long int d, unsigned long int g, float *a)
  87. {
  88.         unsigned long int l, p, s;
  89.                 float v, u;
  90.         l = d; p = g;
  91.         s = (d + g)/2;
  92.         v = a[s];
  93.         do
  94.         {
  95.                 while (a[l] < v) l = l + 1;
  96.                 while (a[p] > v) p = p - 1;
  97.                 if (l <= p)
  98.                 {
  99.                         u = a[l];
  100.                         a[l] = a[p];
  101.                         a[p] = u;
  102.                         l = l + 1; p = p - 1;
  103.                 }
  104.         } while (l <= p);
  105.         if (d < p) quick_sort(d, p, a);
  106.         if (l < g) quick_sort(l, g, a);
  107. }
  108.  
  109.  
  110. int main()
  111. {
  112.         float * a = new float[n];
  113.         unsigned long int m;
  114.         int k;
  115.         time_t t;
  116.         srand((unsigned)time(&t));
  117.         clock_t tp, tk;
  118.         double tc;
  119.         cout << "Podaj ilosc wyrazow ciagu ";
  120.         cin >> m;
  121.         //cout << "ciag wylosowany" << "\n";
  122.         for (unsigned long int i = 1; i <= m; i++)
  123.         {
  124.  
  125.                 a[i] = rand() % 10000;
  126.                 //cout << a[i] << "\t";
  127.         }
  128.         //cout << "\n";
  129.         do
  130.         {
  131.                 cout << "Podaj procedury" << "\n" << "1: Procedura babelkowa" << "\n" << "2: Procedura wstawianie" << "\n" << "3: Procedura scalania" << "\n" << "4: Procedura quick sort" << endl;
  132.                 cin >> k;
  133.                 switch (k)
  134.                 {
  135.                 case 1:
  136.                 {
  137.                                   cout << "Wybrales sortowanie babelkowe ";
  138.                                   tp = clock();
  139.                                   bubble_sort(m, a);
  140.                                   tk = clock();
  141.                                   break;
  142.                 }
  143.                 case 2:{
  144.                                    cout << "Wybrales sortowanie wstawianie ";
  145.                                    tp = clock();
  146.                                    sort_insert(m, a);
  147.                                    tk = clock();
  148.                                    break;
  149.                 }
  150.                 case 3:{
  151.                                    cout << "Wybrales sortowanie scalanie ";
  152.                                    tp = clock();
  153.                                    sort_scal(1, m, a);
  154.                                    tk = clock();
  155.                                    break;
  156.                 }
  157.                 case 4:{
  158.                                    cout << "Wybrales sortowanie quick sort ";
  159.                                    tp = clock();
  160.                                    quick_sort(1, m, a);
  161.                                    tk = clock();
  162.                                    break;
  163.                 }
  164.                        
  165.                 case 0:{
  166.                                    break;
  167.                 }
  168.  
  169.                 }
  170.                 //cout << "ciag posortowany" << "\n";
  171.  
  172.                 for (unsigned long int i = 1; i <= m; i++)
  173.                         //cout << a[i] << "\t";
  174.                 //cout << "\n";
  175.  
  176.                 tc = (tk - tp) / double(CLOCKS_PER_SEC);
  177.                 cout << "Czas sortowania = " << tc << "\n";
  178.         } while (k != 0);
  179.         return 0;
  180. }