- #include "stdafx.h"
- #include "time.h"
- #include <iostream>
- using namespace std;
- unsigned long int const n = 20000000;
- float z[n+1];
- void bubble_sort(unsigned long int n, float *a)
- {
- unsigned long int l, k;
- float p;
- l = n;
- do
- {
- l = l - 1; k = 0;
- for (unsigned long int i = 1; i <= l; i++)
- if (a[i] > a[i + 1])
- {
- p = a[i]; a[i] = a[i + 1]; a[i + 1] = p; k = k + 1;
- }
- } while (k != 0);
- }
- void sort_insert(unsigned long int n, float *a)
- {
- float y, w;
- unsigned long int l, p, s, k;
- w = -1.7e38;
- a[0] = w;
- for (unsigned long int i = 2; i <= n; i++)
- {
- y = a[i]; l = 0; p = i - 1;
- do
- {
- s = (l + p + 1) / 2;
- if (a[s] <= y)l = s; else p = s - 1;
- } while (l != p);
- k = l;
- for (unsigned long int j = i - 1; j >= k + 1; j--)
- a[j + 1] = a[j];
- a[k + 1] = y;
- }
- }
- void scaluj(unsigned long int l, unsigned long int s, unsigned long int p, float *a)
- {
- //float z[n + 1];
- unsigned long int i, j, m, k;
- i = l; j = s; m = l;
- do
- {
- if (a[i] <= a[j])
- {
- z[m] = a[i]; i = i + 1;
- }
- else { z[m] = a[j]; j = j + 1; }
- m = m + 1;
- } while (i < s && j <= p);
- if (i < s)
- {
- k = p;
- for (unsigned long int j = s - 1; j >= i; j--)
- {
- a[k] = a[j];
- k = k - 1;
- }
- }
- for (unsigned long int i = l; i <= m - 1; i++)
- a[i] = z[i];
- }
- void sort_scal(unsigned long int d, unsigned long int g, float *a)
- {
- unsigned long int s;
- if (d < g)
- {
- s = (d + g) / 2;
- sort_scal(d, s, a);
- sort_scal(s + 1, g, a);
- scaluj(d, s + 1, g, a);
- }
- }
- void quick_sort(unsigned long int d, unsigned long int g, float *a)
- {
- unsigned long int l, p, s;
- float v, u;
- l = d; p = g;
- s = (d + g)/2;
- v = a[s];
- do
- {
- while (a[l] < v) l = l + 1;
- while (a[p] > v) p = p - 1;
- if (l <= p)
- {
- u = a[l];
- a[l] = a[p];
- a[p] = u;
- l = l + 1; p = p - 1;
- }
- } while (l <= p);
- if (d < p) quick_sort(d, p, a);
- if (l < g) quick_sort(l, g, a);
- }
- int main()
- {
- float * a = new float[n];
- unsigned long int m;
- int k;
- time_t t;
- srand((unsigned)time(&t));
- clock_t tp, tk;
- double tc;
- cout << "Podaj ilosc wyrazow ciagu ";
- cin >> m;
- //cout << "ciag wylosowany" << "\n";
- for (unsigned long int i = 1; i <= m; i++)
- {
- a[i] = rand() % 10000;
- //cout << a[i] << "\t";
- }
- //cout << "\n";
- do
- {
- cout << "Podaj procedury" << "\n" << "1: Procedura babelkowa" << "\n" << "2: Procedura wstawianie" << "\n" << "3: Procedura scalania" << "\n" << "4: Procedura quick sort" << endl;
- cin >> k;
- switch (k)
- {
- case 1:
- {
- cout << "Wybrales sortowanie babelkowe ";
- tp = clock();
- bubble_sort(m, a);
- tk = clock();
- break;
- }
- case 2:{
- cout << "Wybrales sortowanie wstawianie ";
- tp = clock();
- sort_insert(m, a);
- tk = clock();
- break;
- }
- case 3:{
- cout << "Wybrales sortowanie scalanie ";
- tp = clock();
- sort_scal(1, m, a);
- tk = clock();
- break;
- }
- case 4:{
- cout << "Wybrales sortowanie quick sort ";
- tp = clock();
- quick_sort(1, m, a);
- tk = clock();
- break;
- }
- case 0:{
- break;
- }
- }
- //cout << "ciag posortowany" << "\n";
- for (unsigned long int i = 1; i <= m; i++)
- //cout << a[i] << "\t";
- //cout << "\n";
- tc = (tk - tp) / double(CLOCKS_PER_SEC);
- cout << "Czas sortowania = " << tc << "\n";
- } while (k != 0);
- return 0;
- }