Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Lab_darbas3_v2.cpp. Trecias laboratorinis darbas: rusiavimo algoritmai.
- //
- #include "stdafx.h"
- #include <iostream>
- #include <algorithm> // atsitiktinai sumaisytu aibiu generavimui su random_shuffle
- #include <vector>
- #include <ctime>
- using namespace std;
- int Pvs, Kvs; // Pvs - palyginimu veiksmu skaicius, Kvs - kopijavimu veiksmu skaicius
- // Iterpimo algorimas (Insertion sort)
- void IterpimoAlgoritmas(vector<int>&masyvas) {
- for (int i = 1; i < (int)masyvas.size(); i++) {
- int v = masyvas[i];
- int j = i;
- Kvs++;
- for (int i = 1; i < (int)masyvas.size(); i++)
- {
- if (masyvas[j - 1] > v)
- {
- Pvs++;
- masyvas[j] = masyvas[j - 1];
- Kvs++;
- j = j - 1;
- if (j == 0) // iseiname is ciklo
- break;
- }
- else
- {
- Pvs++;
- break;
- }
- }
- masyvas[j] = v;
- }
- }
- int partition(vector<int> &masyvas, int start, int end)
- {
- int pivot = masyvas[end];
- int pind = start;
- int t;
- for (int i = start; i<end; i++)
- {
- if (masyvas[i] <= pivot)
- {
- Pvs++;
- //swap
- t = masyvas[i];
- masyvas[i] = masyvas[pind];
- masyvas[pind] = t;
- pind++;
- Kvs = Kvs + 3;
- }
- else
- Pvs++;
- }
- //swap
- t = masyvas[end];
- masyvas[end] = masyvas[pind];
- masyvas[pind] = t;
- Kvs = Kvs + 3;
- return pind;
- }
- // spartusis rusiavimo algorimas (Quick sort)
- void SpartusisAlgoritmas(vector<int> &masyvas, int start, int end) {
- if (start<end)
- {
- int pivot_ind = partition(masyvas, start, end);
- SpartusisAlgoritmas(masyvas, start, pivot_ind - 1);
- SpartusisAlgoritmas(masyvas, pivot_ind + 1, end);
- }
- }
- void Duom_seka(vector<int> &masyvas, int N)
- {
- // generuojame masyva:
- for (int i = 1; i <= N; i++)
- masyvas.push_back(i);
- // inicializuojame atsitiktiniu skaiciu generatoriu:
- srand(N);
- // Atsitiktinai sumaisome masyva:
- random_shuffle(masyvas.begin(), masyvas.end());
- }
- // Iterpimo r.a. - laiko matavimas
- void Iterpimo_laiko_mat(int N, int K)
- {
- vector<int> masyvas;
- Duom_seka(masyvas, N);
- clock_t start = clock(); // matuojam laika
- for (int k = 0; k < K; k++) // kartojimu ciklas laiku matavimui
- {
- IterpimoAlgoritmas(masyvas);
- }
- clock_t end = clock();
- double laikas = (double)(end - start) / (CLOCKS_PER_SEC * K) * 1000;
- cout << ", laikas = " << laikas << " (ms)" << endl;
- }
- // Spartusis r.a. - laiko matavimas
- void Spartusis_laiko_mat(int N, int K)
- {
- vector<int> masyvas;
- Duom_seka(masyvas, N);
- clock_t start = clock(); // matuojam laika
- for (int k = 0; k < K; k++) // kartojimu ciklas laiku matavimui
- {
- SpartusisAlgoritmas(masyvas, 0, masyvas.size() - 1);
- }
- clock_t end = clock();
- double laikas = (double)(end - start) / (CLOCKS_PER_SEC * K) * 1000;
- cout << ", laikas = " << laikas << " (ms)" << endl;
- }
- // Iterpimo r.a. - kopijavimu ir palyginimu skaiciu matavimas
- void Iterpimo_VS_mat(int &Pvs, int &Kvs, int N)
- {
- vector<int> masyvas;
- Duom_seka(masyvas, N);
- IterpimoAlgoritmas(masyvas);
- cout << "Kai N = " << N << ", palyginimu VS = " << Pvs << ", kopijavimu VS = " << Kvs;
- }
- // Spartusis r.a. - kopijavimu ir palyginimu skaiciu matavimas
- void Spartusis_VS_mat(int &Pvs, int &Kvs, int N)
- {
- vector<int> masyvas;
- Duom_seka(masyvas, N);
- SpartusisAlgoritmas(masyvas, 0, masyvas.size() - 1);
- cout << "Kai N = " << N << ", palyginimu VS = " << Pvs << ", kopijavimu VS = " << Kvs;
- }
- int main()
- {
- int N = 0, K=10000; // aibes elementu skaicius
- cout << "Iterpimo rusiavimo algoritmas\n\n";
- for (int i = 0; i < 8; i++)
- {
- N = N + 100;
- Pvs = 0;
- Kvs = 0;
- Iterpimo_VS_mat(Pvs, Kvs, N);
- Iterpimo_laiko_mat(N,K);
- }
- N = 0;
- cout << "\n\nSpartusis rusiavimo algoritmas\n\n";
- for (int i = 0; i < 8; i++)
- {
- N = N + 100;
- Pvs = 0;
- Kvs = 0;
- Spartusis_VS_mat(Pvs, Kvs, N);
- Spartusis_laiko_mat(N,K);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement