Advertisement
naffaer

12 srand s.babelkowo i s.quick c++

Mar 19th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <time.h>
  3. #include <windows.h>
  4.  
  5. using namespace std;
  6.  
  7. int ile;
  8. clock_t start,stop;
  9. double czas;
  10.  
  11. void sortowanie_babelkowe(int *tab, int n)
  12. {
  13.     for(int i=1; i<n; i++)
  14.     {
  15.         for(int j=n-1; j>=1; j--)
  16.         {
  17.             if(tab[j]<tab[j-1])
  18.             {
  19.                 int bufor;
  20.                 bufor=tab[j-1];
  21.                 tab[j-1]=tab[j];
  22.                 tab[j]=bufor;
  23.             }
  24.         }
  25.     }
  26. }
  27.  
  28. void quicksort(int *tablica, int lewy, int prawy)
  29. {
  30.     int v=tablica[(lewy+prawy)/2];
  31.     int i,j,x;
  32.     i=lewy;
  33.     j=prawy;
  34.     do
  35.     {
  36.         while(tablica[i]<v) i++;
  37.         while(tablica[j]>v) j--;
  38.         if(i<=j)
  39.         {
  40.             x=tablica[i];
  41.             tablica[i]=tablica[j];
  42.             tablica[j]=x;
  43.             i++;
  44.             j--;
  45.         }
  46.     }
  47.     while(i<=j);
  48.     if(j>lewy) quicksort(tablica,lewy, j);
  49.     if(i<prawy) quicksort(tablica, i, prawy);
  50. }
  51.  
  52. int main()
  53. {
  54.     cout << "Porownanie czasow sortowania v.1" << endl;
  55.  
  56.     cout<<"Ile losowych liczb w tablicy: ";
  57.     cin>>ile;
  58.  
  59.     //dynamiczna alokacja tablicy
  60.     int *tablica;
  61.     tablica=new int [ile];
  62.  
  63.     int *tablica2;
  64.     tablica2=new int [ile];
  65.  
  66.     //inicjowanie generatora
  67.     srand(time(NULL));
  68.  
  69.     //wczytywanie losowych liczb do tablicy
  70.     for(int i=0; i<ile; i++)
  71.     {
  72.         tablica[i] = rand()%100000+1;
  73.     }
  74.  
  75.     //przepisanie tablicy do tablicy2
  76.     for(int i=0; i<ile; i++)
  77.     {
  78.        tablica2[i]=tablica[i];
  79.     }
  80.  
  81.  
  82.         cout<<"Przed posortowaniem: "<<endl;
  83.         for(int i=0; i<ile; i++)
  84.         {
  85.             cout<<tablica2[i]<<" ";
  86.         }
  87.  
  88.     cout<<endl<<"Sortuje teraz babelkowo. Prosze czekac!"<<endl;
  89.     start = clock();
  90.     sortowanie_babelkowe(tablica,ile);
  91.     stop = clock();
  92.     czas = (double)(stop-start) / CLOCKS_PER_SEC;
  93.     cout<<endl<<"Czas sortowania babelkowego: "<<czas<<" s"<<endl;
  94.  
  95.     cout<<endl<<"Sortuje teraz algorytmem quicksort. Prosze czekac!"<<endl;
  96.     start = clock();
  97.     quicksort(tablica2, 0, ile-1);
  98.     stop = clock();
  99.     czas = (double)(stop-start) / CLOCKS_PER_SEC;
  100.     cout<<endl<<"Czas sortowania quicksort: "<<czas<<" s"<<endl;
  101.  
  102.  
  103.        cout<<"Po posortowaniu: "<<endl;
  104.         for(int i=0; i<ile; i++)
  105.         {
  106.             cout<<tablica[i]<<" ";
  107.         }
  108.  
  109.  
  110.     delete [] tablica;
  111.     delete [] tablica2;
  112.  
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement